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)

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