Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

DOI10.1007/978-3-642-11409-0_4zbMath1273.05216OpenAlexW1883368305WikidataQ60488607 ScholiaQ60488607MaRDI QIDQ5851092

Daniël Paulusma, Fedor V. Fomin, Pim van 't Hof, Hajo J. Broersma

Publication date: 21 January 2010

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11409-0_4

zbMATH Keywords

algorithmclaw-free graphclosed trailNP-complete problemedge dominationHamiltonian cycle problemeulerian subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

Exact algorithms for finding longest cycles in claw-free graphs ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

This page was built for publication: Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs