A note on the complexity of longest path problems related to graph coloring

DOI10.1016/S0893-9659(04)90003-1zbMath1039.05036OpenAlexW1975581618MaRDI QIDQ1433224

Panos M. Pardalos, Athanasios Migdalas

Publication date: 15 June 2004

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0893-9659(04)90003-1

zbMATH Keywords

ComplexityGraph coloringLongest path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Formally verified algorithms for upper-bounding state space diameters ⋮ On the complexity of path problems in properly colored directed graphs

Uses Software

• GRAFFITI

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the complexity of longest path problems related to graph coloring