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

DOI10.1016/j.dam.2007.06.001zbMath1127.05079OpenAlexW2092747350MaRDI QIDQ2457005

Maw-Shang Chang, Ruo-Wei Hung

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

distance-hereditary graphsHamiltonian pathpath coverGraph algorithms

Mathematics Subject Classification ID

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

Related Items (13)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ On finding the best and worst orientations for the metric dimension ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ Path covering number and \(L(2,1)\)-labeling number of graphs ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Minimum constellation covers: hardness, approximability and polynomial cases ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Distance-hereditary graphs
• On mapping processes to processors in distributed systems
• Complement reducible graphs
• Optimal covering of cacti by vertex-disjoint paths
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Optimal path cover problem on block graphs and bipartite permutation graphs
• The path-partition problem in block graphs
• An optimal path cover algorithm for cographs
• Optimal path cover problem on block graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• The Hamiltonian problem on distance-hereditary 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 Recognition Algorithm for Cographs
• A characterization of ptolemaic graphs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

This page was built for publication: Finding a minimum path cover of a distance-hereditary graph in polynomial time