Abstract. In this paper, we study the problem of ecologically coloring a graph. Intuitively, an ecologicalc oloring 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 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.

Crescenzi, P., DI IANNI, M., Greco, F., Rossi, G., Vocca, P. (2008). Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings. In Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008. (pp.90-100). Springer-Verlag [10.1007/978-3-540-92248-3_9].

Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings

DI IANNI, MIRIAM;ROSSI, GIANLUCA;
2008

Abstract

Abstract. In this paper, we study the problem of ecologically coloring a graph. Intuitively, an ecologicalc oloring 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 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.
WG 2008
Durham University, U.K.
30 June - 2 July 2008
Rilevanza internazionale
Settore INF/01 - Informatica
English
algorithms, role assignment, graph theory
Intervento a convegno
Crescenzi, P., DI IANNI, M., Greco, F., Rossi, G., Vocca, P. (2008). Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings. In Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008. (pp.90-100). Springer-Verlag [10.1007/978-3-540-92248-3_9].
Crescenzi, P; DI IANNI, M; Greco, F; Rossi, G; Vocca, P
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/9684
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact