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
cocomparability graphsposetsHamiltonian path problembump numberminimum path cover problemlexicographic depth first search
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
- Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability 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
- Graphs with at most two moplexes
- Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
- A simple polynomial algorithm for the longest path problem on cocomparability graphs
- 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
- A simple linear time algorithm to solve the MIST problem on interval graphs
- Title not available (Why is that?)
- 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
- Maximum induced matching algorithms via vertex ordering characterizations
- Parameterizing path partitions
- End-Vertices of Graph Search Algorithms
- 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
- The Recognition Problem of Graph Search Trees
- A new graph parameter to measure linearity
- Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
- 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)
