The longest path problem has a polynomial solution on interval graphs

DOI10.1007/s00453-010-9411-3zbMath1236.05114OpenAlexW2119014043WikidataQ56639272 ScholiaQ56639272MaRDI QIDQ639287

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

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

complexitydynamic programmingpolynomial algorithminterval graphslongest path problem

Mathematics Subject Classification ID

Dynamic programming (90C39) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (15)

A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Parameterized complexity of multicut in weighted trees ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Dendrograms, minimum spanning trees and feature selection ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Contracting to a longest path in H-free graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

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
• A note on the Hamiltonian circuit problem on directed path 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
• The 1-fixed-endpoint path cover problem is Polynomial on interval 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
• Deferred-query: An efficient approach for some problems on interval graphs
• Hamilton Paths in Grid Graphs
• Algorithms and Computation

This page was built for publication: The longest path problem has a polynomial solution on interval graphs