Title of article :
A note on the complexity of longest path problems related to graph coloring
Original Research Article
Author/Authors :
P.M. Pardalos، نويسنده , , A. Migdalas، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Abstract :
In this note, we show that some problems related to the length of the longest simple path from a given vertex in a graph are NP-complete. We also discuss an extension to the graph coloring problem.
Keywords :
Longest path , Graph coloring , Complexity
Journal title :
Applied Mathematics Letters
Journal title :
Applied Mathematics Letters
