✦ 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
DOI: 10.1016/s0893-9659(04)90003-1

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 descriptive complexity of

A note on the descriptive complexity of maximization problems

✍ Pierluigi Crescenzi; Riccardo Silvestri 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 375 KB

On a class of metrics related to graph l

On a class of metrics related to graph layout problems

✍ Adam N. Letchford; Gerhard Reinelt; Hanna Seitz; Dirk Oliver Theis 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 296 KB

A note on the problem of updating shorte

A note on the problem of updating shortest paths

✍ Satoru Fujishige 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

Notes on problems related to the care of

Notes on problems related to the care of patients overseas

✍ B.E.C. Hopwood 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 404 KB

The Complexity of Defining a Relation on

The Complexity of Defining a Relation on a Finite Graph

✍ L. Babai; Gy. Turán 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 702 KB

A note on the space complexity of some d

A note on the space complexity of some decision problems for finite automata

✍ 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.