The longest path problem is polynomial on cocomparability graphs

DOI10.1007/S00453-011-9583-5zbMATH Open1259.68094OpenAlexW2106934213WikidataQ56639277 ScholiaQ56639277MaRDI QIDQ1939666FDOQ1939666

Authors: Kyriaki Ioannidou, Stavros D. Nikolopoulos 

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

Recommendations

• The longest path problem is polynomial on cocomparability graphs
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• Algorithms and Computation

zbMATH Keywords

complexitycocomparability graphspolynomial algorithmpermutation graphslongest path problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Finding Hamiltonian circuits in proper interval graphs
• On computing a longest path in a tree
• Algorithmic graph theory and perfect graphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Finding Long Paths, Cycles and Circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Finding Paths and Cycles of Superpolylogarithmic Length
• Simple Geometrical Intersection Graphs
• Algorithms and Computation
• On approximating the longest path in a graph
• Linear algorithm for optimal path cover problem on interval graphs
• HAMILTONian circuits in chordal bipartite graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Computing the bump number is easy
• Paths in interval graphs and circular arc graphs
• Finding large cycles in Hamiltonian graphs
• Title not available (Why is that?)
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• A note on the Hamiltonian circuit problem on directed path graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Title not available (Why is that?)
• The longest path problem has a polynomial solution on interval graphs
• Algorithms for long paths in graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs

Cited In (12)

• The longest cycle problem is polynomial on interval graphs
• The longest path problem is polynomial on cocomparability graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Nonempty intersection of longest paths in series-parallel graphs
• On computing longest paths in small graph classes
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Contracting to a longest path in H-free graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• The longest path problem in odd-sized \(O\)-shaped grid graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939666)