The Longest Path Problem is Polynomial on Cocomparability Graphs

DOI10.1007/978-3-642-16926-7_5zbMath1308.68065OpenAlexW1541438895MaRDI QIDQ3057610

Kyriaki Ioannidou, Stavros D. Nikolopoulos

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_5

zbMATH Keywords

complexitypolynomial algorithmcocomparability graphspermutation 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 (3)

Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs ⋮ Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for long paths in graphs
• Linear algorithm for optimal path cover problem on interval 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
• The Longest Path Problem Is Polynomial on Interval Graphs
• Finding paths and cycles of superpolylogarithmic length
• Finding Long Paths, Cycles and Circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Deferred-query: An efficient approach for some problems on interval graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Hamilton Paths in Grid Graphs
• Simple Geometrical Intersection Graphs
• Algorithms and Computation

This page was built for publication: The Longest Path Problem is Polynomial on Cocomparability Graphs