We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes. © Springer Science+Business Media, LLC 2011.
On the complexity of path problems in properly colored directed graphs
Granata D;
2012
Abstract
We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes. © Springer Science+Business Media, LLC 2011.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.
