The Longest Path Problem Is Polynomial on Interval Graphs

DOI10.1007/978-3-642-03816-7_35zbMath1250.68128OpenAlexW1580484824MaRDI QIDQ3182942

Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/9296/1/9296.pdf

zbMATH Keywords

complexitydynamic programmingpolynomial algorithminterval graphslongest path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The longest cycle problem is polynomial on interval graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Tropical paths in vertex-colored graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs ⋮ Sitting closer to friends than enemies, revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Algorithms for long paths in graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• A unified approach to domination problems on interval graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Paths in interval graphs and circular arc graphs
• On computing a longest path in a tree
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Finding paths and cycles of superpolylogarithmic length
• Finding Long Paths, Cycles and Circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Algorithms and Computation

This page was built for publication: The Longest Path Problem Is Polynomial on Interval Graphs