Name
Title | ||
|---|---|---|
Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings |
Abstract | ||
|---|---|---|
In this paper, we study the problem of ecologically coloring a graph. Intuitively, an ecological coloring of a graph is a role assignment to the nodes of the graph, such that two nodes surrounded by the same set of roles must be assigned the same role (Borgatti and Everett, 1992). We prove that, for any simple undirected graph G with n G distinct neighborhoods and for any integer k with 1 ≤ k ≤ n G , G admits an ecological coloring which uses exactly k roles, and that this coloring can be computed in polynomial time. Our result strongly contrasts with the NP-completeness result of the regular coloring problem, where it is required that two nodes with the same role must be surrounded by the same set of roles (Fiala and Paulusma, 2005). Hence, we conclude that not only the ecological coloring is easier to understand as a model of social relationships (Borgatti and Everett, 1994), but it is also feasible from a computational complexity point of view. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92248-3_9 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
np-completeness result,computational complexity point,distinct neighborhood,simple undirected graph,ecological coloring,role assignment feasible,polynomial-time algorithm,integer k,role assignment,computing ecological colorings,k role,n g,regular coloring problem,polynomial time,computational complexity | Conference | 5344 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.40 |
References | Authors | |
7 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| pilu crescenzi | 1 | 95 | 11.52 |
| Miriam di Ianni | 2 | 144 | 17.27 |
| Federico Greco | 3 | 6 | 2.06 |
| Gianluca Rossi | 4 | 235 | 21.60 |
| Paola Vocca | 5 | 225 | 24.79 |