Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
From MaRDI portal
Publication:2566023
DOI10.1016/j.tcs.2005.04.009zbMath1077.68074OpenAlexW1989983876MaRDI QIDQ2566023
Publication date: 22 September 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.04.009
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (16)
Cyclability in graph classes ⋮ Unnamed Item ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ 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 ⋮ Distance-hereditary comparability graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval 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 ⋮ 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
- Completely separable graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Distance-hereditary graphs
- Hamiltonian circuits in interval graph generalizations
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- A note on the Hamiltonian circuit problem on directed path graphs
- Graph classes between parity and distance-hereditary graphs
- MAD trees and distance-hereditary graphs
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Centers and medians of distance-hereditary graphs
- An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
- HAMILTONian circuits in chordal bipartite graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Graph Classes: A Survey
- Deferred-query: An efficient approach for some problems on interval graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Hamilton Paths in Grid Graphs
- A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Domination in distance-hereditary graphs
- Compact-port routing models and applications to distance-hereditary graphs
This page was built for publication: Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
