An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs (Articolo in rivista)

Type
Label
  • An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs (Articolo in rivista) (literal)
Anno
  • 2002-01-01T00:00:00+01:00 (literal)
Alternative label
  • 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
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Confessore, G.; Dell'Olmo, P.; Giordani, S. (literal)
Pagina inizio
  • 73 (literal)
Pagina fine
  • 90 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 120 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • CNR, Università Roma La Sapienza, Università Roma Tor Vergata (literal)
Titolo
  • An Approximation Result for the Interval Coloring Problem on Claw-free Chordal Graphs (literal)
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. (literal)
Autore CNR

Incoming links:


Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it