Finding a minimum path cover of a distance-hereditary graph in polynomial time

DOI10.1016/J.DAM.2007.06.001MaRDI QIDQ2457005zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Hamiltonian pathpath coverdistance-hereditary graphsGraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3465355 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 205350 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A characterization of ptolemaic graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• An optimal path cover algorithm for cographs
• Complement reducible graphs
• Completely separable graphs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• Distance-hereditary graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Linear algorithm for optimal path cover problem on interval graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• On Path Cover Problems in Digraphs and Applications to Program Testing
• On mapping processes to processors in distributed systems
• On the clique-width of some perfect graph classes
• Optimal covering of cacti by vertex-disjoint paths
• Optimal path cover problem on block graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• The Hamiltonian problem on distance-hereditary graphs
• The path-partition problem in block graphs
• Upper bounds to the clique width of 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)