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. (C) 2002 Elsevier Science B.V. All rights reserved.
Confessore, G., Dell'Olmo, P., Giordani, S. (2002). An approximation result for the interval coloring problem on claw-free chordal graphs. In DISCRETE APPLIED MATHEMATICS (pp.73-90). AMSTERDAM : ELSEVIER SCIENCE BV.
An approximation result for the interval coloring problem on claw-free chordal graphs
GIORDANI, STEFANO
2002-01-01
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 made. (C) 2002 Elsevier Science B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.