|
|||||
|
|
On the complexity of path problems in properly colored directed graphs |
|
| Authors: | Donatella Granata Behnam Behdani Panos M. Pardalos |
| Affiliation: | 1. Department of Statistics, Probability and Applied Statistics, University of Rome “La Sapienza”, P.le Aldo Moro 5, Rome, Italy 2. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL, 32611, USA 3. Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL, 32611, USA |
| 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 $mathcal{X}(G)$ stable subsets, where $mathcal{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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |