Exact algorithms for finding longest cycles in claw-free graphs

DOI10.1007/S00453-011-9576-4MaRDI QIDQ1939671zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Pim Van 't Hof, Daniël Paulusma, Hajo 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) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Fast exact algorithms for Hamiltonicity in claw-free graphs
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• scientific article; zbMATH DE number 1420921
• Counting closed trails
• Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs

Cites work

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

Cited in

(11)

• Counting closed trails
• Declawing a graph: polyhedra and branch-and-cut algorithms
• The longest cycle problem is polynomial on interval graphs
• Finding a smallest odd hole in a claw-free graph using global structure
• Theory and application of reciprocal transformation of “path problem” and “time float problem”
• scientific article; zbMATH DE number 44783 (Why is no real title available?)
• scientific article; zbMATH DE number 205838 (Why is no real title available?)
• Exact Solution Algorithms for the Chordless Cycle Problem
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Fast exact algorithms for Hamiltonicity in claw-free graphs
• Exact methods for the longest induced cycle problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939671)