LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs

DOI10.1137/11083856XzbMATH Open1272.05192OpenAlexW1986137691MaRDI QIDQ2848201FDOQ2848201

Authors Barnaby Dalton, Derek G. Corneil, Michel Habib

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

cocomparability graphsposetsHamiltonian path problembump numberminimum path cover problemlexicographic depth first search

Mathematics Subject Classification ID

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

Recommendations

• Corrigendum to: ``LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• An optimal path cover algorithm for cographs
• An approximation algorithm for the minimum co-path set problem
• Complexity and approximability of minimum path-collection exact covers
• A new LBFS-based algorithm for cocomparability graph recognition
• On the minimum cycle cover problem on graphs with bounded co-degeneracy
• A time-optimal solution for the path cover problem on cographs.
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

Cited in

(33)

• The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs
• Graph searches and their end vertices
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• Vertex ordering characterizations of graphs of bounded asteroidal number
• Parameterizing path partitions
• A new LBFS-based algorithm for cocomparability graph recognition
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Graph Search Trees and Their Leaves
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• A simple certifying algorithm for 3-edge-connectivity
• Semi-proper interval graphs
• 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
• End-vertices of graph search algorithms
• Recognizing graph search trees
• Graphs with at most two moplexes
• Parameterizing path partitions
• Cyclability in graph classes
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A linear-time certifying algorithm for recognizing generalized series-parallel graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Certifying induced subgraphs in large graphs
• The recognition problem of graph search trees
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• The longest cycle problem is polynomial on interval graphs
• Nontrivial path covers of graphs: existence, minimization and maximization
• Corrigendum to: ``LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matching algorithms via vertex ordering characterizations
• A simple linear time algorithm to solve the MIST problem on interval graphs

This page was built for publication: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs

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