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

PRAMParallel algorithmsHamiltonian problemDistance-hereditary graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) 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

• 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?)
• 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, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Efficient parallel recognition of cographs
• 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

(18)

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