The Hamiltonian problem on distance-hereditary graphs

DOI10.1016/J.DAM.2005.07.012MaRDI QIDQ2489947zbMATH OpenOpenAlexFDO

Authors Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.07.012

zbMATH Keywords

Distance-hereditary graphsHamiltonian problemParallel algorithmsPRAM

Mathematics Subject Classification ID

Distance in graphs (05C12) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 2089962
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• A simple parallel tree contraction algorithm
• A time-optimal solution for the path cover problem on cographs.
• Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
• Completely separable graphs
• Distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Dominating cliques in distance-hereditary graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Efficient parallel recognition of cographs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
• The path-partition problem in bipartite distance-hereditary graphs
• Tree-based parallel algorithm design
• Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
• Weighted connected domination and Steiner trees in distance-hereditary graphs

Cited in

(20)

• Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs
• Laminar structure of ptolemaic graphs with applications
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Hamilton cycles in almost distance-hereditary graphs
• scientific article; zbMATH DE number 1303031 (Why is no real title available?)
• Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
• scientific article; zbMATH DE number 815104 (Why is no real title available?)
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
• Hamiltonian path in permutation graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Cyclability in graph classes
• A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This page was built for publication: The Hamiltonian problem on distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489947)