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.
Titolo: | Coloring Circular Arcs with Applications |
Autori: | |
Data di pubblicazione: | 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. |
Handle: | http://hdl.handle.net/11386/1000142 |
ISBN: | 1894145070 |
Appare nelle tipologie: | 4.1.2 Proceedings con ISBN |
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.