We are given a edge-weighted undirected graph G = (V, E) and a set of labels/colors C = {1, 2, . . . , p}. A non-empty subset C_v in C is associated with each vertex v in V. A coloring of the vertices is feasible if each vertex v is colored with a color of C_v. A coloring uniquely defines a subset E_0 in E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E_0 is, in general, NP-hard. In this work we first propose polynomial time algorithms for some special cases, namely when the input graph is a tree, a cactus or with bounded tree-width. Then, an implicit enumeration scheme for finding an optimal coloring in the general case is described and computational results are presented.

Alfieri, A., Nicosia, G., Pacifici, A. (2006). Exact algorithms for a discrete metric labeling problem. DISCRETE OPTIMIZATION, 3, 181-194 [10.1016/j.disopt.2006.05.009].

Exact algorithms for a discrete metric labeling problem

NICOSIA, GAIA;
2006

Abstract

We are given a edge-weighted undirected graph G = (V, E) and a set of labels/colors C = {1, 2, . . . , p}. A non-empty subset C_v in C is associated with each vertex v in V. A coloring of the vertices is feasible if each vertex v is colored with a color of C_v. A coloring uniquely defines a subset E_0 in E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E_0 is, in general, NP-hard. In this work we first propose polynomial time algorithms for some special cases, namely when the input graph is a tree, a cactus or with bounded tree-width. Then, an implicit enumeration scheme for finding an optimal coloring in the general case is described and computational results are presented.
Alfieri, A., Nicosia, G., Pacifici, A. (2006). Exact algorithms for a discrete metric labeling problem. DISCRETE OPTIMIZATION, 3, 181-194 [10.1016/j.disopt.2006.05.009].
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/11590/157418
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact