On the complexity of path problems in properly colored directed graphs
From MaRDI portal
Publication:1928492
DOI10.1007/s10878-011-9401-7zbMath1261.05025MaRDI QIDQ1928492
Panos M. Pardalos, Behnam Behdani, Donatella Granata
Publication date: 3 January 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-011-9401-7
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
05C20: Directed graphs (digraphs), tournaments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Variations on the Roy-Gallai theorem
- The Euclidean traveling salesman problem is NP-complete
- A note on the complexity of longest path problems related to graph coloring
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- A generalization of the Gallai-Roy theorem