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

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

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)

Cited In (34)

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

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)