LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs

DOI10.1137/11083856XzbMath1272.05192OpenAlexW1986137691MaRDI QIDQ2848201

Barnaby Dalton, Michel A. Habib, Derek Gordon Corneil

Publication date: 25 September 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/11083856x

zbMATH Keywords

posets cocomparability graphs Hamiltonian path problem bump number minimum path cover problem lexicographic depth first search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (26)

A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs ⋮ On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ Cyclability in graph classes ⋮ Recognizing graph search trees ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Graph searches and their end vertices ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ End-Vertices of Graph Search Algorithms ⋮ Parameterizing path partitions ⋮ A tie-break model for graph search ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Unnamed Item ⋮ A simple certifying algorithm for 3-edge-connectivity ⋮ A new graph parameter to measure linearity ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ The Recognition Problem of Graph Search Trees ⋮ Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

This page was built for publication: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs