The longest path problem is polynomial on cocomparability graphs

DOI10.1007/s00453-011-9583-5zbMath1259.68094OpenAlexW2106934213WikidataQ56639277 ScholiaQ56639277MaRDI QIDQ1939666

Stavros D. Nikolopoulos, Kyriaki Ioannidou

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9583-5

zbMATH Keywords

complexitypolynomial algorithmcocomparability graphspermutation graphslongest path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Contracting to a longest path in H-free graphs ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The longest path problem has a polynomial solution on interval graphs
• 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 large cycles in Hamiltonian graphs
• Finding Hamiltonian circuits in proper interval graphs
• Computing the bump number is easy
• 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 Long Paths, Cycles and Circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Hamilton Paths in Grid Graphs
• Finding Paths and Cycles of Superpolylogarithmic Length
• Simple Geometrical Intersection Graphs
• Algorithms and Computation

This page was built for publication: The longest path problem is polynomial on cocomparability graphs