On the complexity of path problems in properly colored directed graphs
From MaRDI portal
Publication:1928492
DOI10.1007/s10878-011-9401-7zbMath1261.05025OpenAlexW2010949955MaRDI 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
Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- 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
- Unnamed Item
This page was built for publication: On the complexity of path problems in properly colored directed graphs