On the complexity of path problems in properly colored directed graphs

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

zbMATH Keywords

complexityshortest pathgraph coloringchromatic numberlongest path

Mathematics Subject Classification ID

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)

Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks

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

This page was built for publication: On the complexity of path problems in properly colored directed graphs