Exact algorithms for finding longest cycles in claw-free graphs

DOI10.1007/s00453-011-9576-4zbMath1259.05162OpenAlexW1970923056WikidataQ60488416 ScholiaQ60488416MaRDI QIDQ1939671

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

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/9020/1/9020.pdf

zbMATH Keywords

Hamiltonian cycle problemlongest cycle problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (4)

Theory and application of reciprocal transformation of “path problem” and “time float problem” ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Computing sharp 2-factors in claw-free graphs
• Dynamic programming meets the principle of inclusion and exclusion
• Claw-free graphs---a survey
• On a closure concept in claw-free graphs
• HAMILTONian circuits in chordal bipartite graphs
• On the complexity of some edge-partition problems for graphs
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Pancyclicity and NP-completeness in planar graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Open problems around exact algorithms
• A Dynamic Programming Approach to Sequencing Problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• An Improved Exact Algorithm for Cubic Graph TSP
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• The Traveling Salesman Problem for Cubic Graphs
• Determinant Sums for Undirected Hamiltonicity
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

This page was built for publication: Exact algorithms for finding longest cycles in claw-free graphs