The Hamiltonian problem on distance-hereditary graphs
From MaRDI portal
Publication:2489947
DOI10.1016/j.dam.2005.07.012zbMath1095.68084OpenAlexW2157955289MaRDI QIDQ2489947
Ming-Tat Ko, Sun-Yuan Hsieh, Tsan-sheng Hsu, Chin-Wen Ho
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (9)
Cyclability in graph classes ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ 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 ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
- Completely separable graphs
- Distance-hereditary graphs
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- The path-partition problem in bipartite distance-hereditary graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Tree-based parallel algorithm design
- A time-optimal solution for the path cover problem on cographs.
- Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
- Efficient parallel recognition of cographs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- A simple parallel tree contraction algorithm
- Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
- A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
- Dominating cliques in distance-hereditary graphs
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
This page was built for publication: The Hamiltonian problem on distance-hereditary graphs
