The circular arc coloring problem is the problem of finding a minimal coloring of a set of arcs on a circle so that if two arcs intersect then they are assigned different colors. When a generic set of circular arcs is to be colored, the problem is known to be NP-complete; we consider certain instances of the problem which can be optimally solved in polynomial time.

Coloring Circular Arcs with Applications

GARGANO, Luisa;RESCIGNO, Adele Anna
2000

Abstract

The circular arc coloring problem is the problem of finding a minimal coloring of a set of arcs on a circle so that if two arcs intersect then they are assigned different colors. When a generic set of circular arcs is to be colored, the problem is known to be NP-complete; we consider certain instances of the problem which can be optimally solved in polynomial time.
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: http://hdl.handle.net/11386/1000142
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact