✦ LIBER ✦

The Longest Path Problem has a Polynomial Solution on Interval Graphs

✍ Scribed by Kyriaki Ioannidou; George B. Mertzios; Stavros D. Nikolopoulos

Book ID: 106149118
Publisher: Springer
Year: 2010
Tongue: English
Weight: 791 KB
Volume: 61
Category: Article
ISSN: 0178-4617
DOI: 10.1007/s00453-010-9411-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Simple Polynomial Algorithm for the Lo

A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

✍ Mertzios, George B.; Corneil, Derek G. 📂 Article 📅 2012 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 333 KB

On approximating the longest path in a g

On approximating the longest path in a graph

✍ D. Karger; R. Motwani; G. D. S. Ramkumar 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 962 KB

An improved algorithm for the longest in

An improved algorithm for the longest induced path problem on -chordal graphs

✍ Tetsuya Ishizeki; Yota Otachi; Koichi Yamazaki 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 181 KB

A polynomial algorithm for the parity pa

A polynomial algorithm for the parity path problem on perfectly orientable graphs

✍ Srinivasa R. Arikati; Uri N. Peled 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 993 KB

A note on the complexity of longest path

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

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

A linear-time algorithm for the longest

A linear-time algorithm for the longest path problem in rectangular grid graphs

✍ Fatemeh Keshavarz-Kohjerdi; Alireza Bagheri; Asghar Asgharian-Sardroud 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 328 KB