๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by P.M. Pardalos; A. Migdalas


Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
194 KB
Volume
17
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

โœฆ Synopsis


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.


๐Ÿ“œ SIMILAR VOLUMES


A note on the space complexity of some d
โœ Tao Jiang; B. Ravikumar ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 533 KB

In this note, we establish the space complexity of decision problems (such as membership, nonemptiness and equivalence) for some finite automata. Our study includes 2-way infinite automata with a pebble.