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.