A simple polynomial algorithm for the longest path problem on cocomparability graphs

DOI10.1137/100793529MaRDI QIDQ4899036zbMATH OpenOpenAlexDBLPWikidataFDO

Authors George B. Mertzios, Derek G. Corneil

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingcocomparability graphspolynomial algorithmlongest path problemlexicographic depth first search

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• The longest path problem is polynomial on cocomparability graphs
• The longest path problem is polynomial on cocomparability graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• Linear time LexDFS on cocomparability graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs

Cited in

(25)

• An approximation algorithm for the longest path problem in solid grid graphs
• The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs
• A polynomial time algorithm for longest paths in biconvex graphs
• Vertex ordering characterizations of graphs of bounded asteroidal number
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Computing and counting longest paths on circular-arc graphs in polynomial time
• On the power of graph searching for cocomparability graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• A tie-break model for graph search
• Linear time LexDFS on cocomparability graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• The longest path problem is polynomial on cocomparability graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Contracting to a longest path in H-free graphs
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• The longest cycle problem is polynomial on interval graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• A genetic algorithm for the picture maze generation problem
• Maximum induced matching algorithms via vertex ordering characterizations
• The Hamiltonian connectivity of rectangular supergrid graphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
• The longest path problem is polynomial on cocomparability graphs

This page was built for publication: A simple polynomial algorithm for the longest path problem on cocomparability graphs

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