A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

DOI10.1137/100793529zbMath1256.05237OpenAlexW1813313303WikidataQ56639274 ScholiaQ56639274MaRDI QIDQ4899036

George B. Mertzios, Derek Gordon 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 programmingpolynomial algorithmcocomparability graphslongest path problemlexicographic depth first search

Mathematics Subject Classification ID

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

Related Items (19)

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 LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Hamiltonian paths, unit-interval complexes, and determinantal facet ideals ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ A tie-break model for graph search ⋮ 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 ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Contracting to a longest path in H-free graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

This page was built for publication: A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs