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

DOI10.1137/100793529zbMATH Open1256.05237DBLPjournals/siamdm/MertziosC12OpenAlexW1813313303WikidataQ56639274 ScholiaQ56639274MaRDI QIDQ4899036FDOQ4899036

Derek G. Corneil, George B. Mertzios

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

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

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)

Cited In (21)

• 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
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• On the power of graph searching for cocomparability graphs
• The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Hamiltonian connectivity of rectangular supergrid graphs
• Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
• 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
• Contracting to a longest path in H-free 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
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
• Polynomial fixed-parameter algorithms: a case study for longest path on interval 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)