We study the problem of 0nding 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 0nding 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 0nd 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.

Confessore, G., Dell'Olmo, P., Giordani, S. (2002). An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs. DISCRETE APPLIED MATHEMATICS, 120, 73-90 [10.1016/S0166-218X(01)00282-7].

An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs

GIORDANI, STEFANO
2002-01-01

Abstract

We study the problem of 0nding 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 0nding 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 0nd 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.
2002
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
Claw-free chordal graphs; Multiprocessor task scheduling; Interval coloring; Approximation algorithm.
http://dx.doi.org/10.1016/S0166-218X(01)00282-7
Confessore, G., Dell'Olmo, P., Giordani, S. (2002). An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs. DISCRETE APPLIED MATHEMATICS, 120, 73-90 [10.1016/S0166-218X(01)00282-7].
Confessore, G; Dell'Olmo, P; Giordani, S
Articolo su rivista
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/52087
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact