Finding a minimum path cover of a distance-hereditary graph in polynomial time
From MaRDI portal
Publication:2457005
DOI10.1016/J.DAM.2007.06.001zbMATH Open1127.05079OpenAlexW2092747350MaRDI QIDQ2457005FDOQ2457005
Authors: Ruo-Wei Hung, Maw-Shang Chang 
Publication date: 29 October 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.06.001
Recommendations
- The path-partition problem in bipartite distance-hereditary graphs
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- scientific article; zbMATH DE number 815104
- An optimal path cover algorithm for cographs
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Complement reducible graphs
- Optimal path cover problem on block graphs and bipartite permutation graphs
- An optimal path cover algorithm for cographs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- On Path Cover Problems in Digraphs and Applications to Program Testing
- On the clique-width of some perfect graph classes
- Linear algorithm for optimal path cover problem on interval graphs
- Distance-hereditary graphs
- On mapping processes to processors in distributed systems
- A Linear Recognition Algorithm for Cographs
- A characterization of ptolemaic graphs
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- The Hamiltonian problem on distance-hereditary graphs
- Optimal covering of cacti by vertex-disjoint paths
- Title not available (Why is that?)
- Completely separable graphs
- Title not available (Why is that?)
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Title not available (Why is that?)
- The path-partition problem in block graphs
- Optimal path cover problem on block graphs
Cited In (17)
- Algorithms for finding disjoint path covers in unit interval graphs
- Path covering number and \(L(2,1)\)-labeling number of graphs
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
- Minimum constellation covers: hardness, approximability and polynomial cases
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- Disjoint path covers with path length constraints in restricted hypercube-like graphs
- A simple linear time algorithm to solve the MIST problem on interval graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- On finding the best and worst orientations for the metric dimension
- Minimum eccentricity shortest paths in some structured graph classes
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor
- A \(5k\)-vertex kernel for 3-path vertex cover
- The Hamiltonian problem on distance-hereditary graphs
This page was built for publication: Finding a minimum path cover of a distance-hereditary graph in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457005)
