A note on the complexity of longest path
โ
P.M. Pardalos; A. Migdalas
๐
Article
๐
2004
๐
Elsevier Science
๐
English
โ 194 KB
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.