We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made
An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graph / Confessore, G; Dell'Olmo, Paolo; Giordani, S.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - (2002), pp. 73-90. [10.1016/S0166-218X(01)00282-7]
An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graph
DELL'OLMO, Paolo;
2002
Abstract
We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were madeI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
