Exact algorithms for finding longest cycles in claw-free graphs

DOI10.1007/S00453-011-9576-4zbMATH Open1259.05162DBLPjournals/algorithmica/BroersmaFHP13OpenAlexW1970923056WikidataQ60488416 ScholiaQ60488416MaRDI QIDQ1939671FDOQ1939671

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

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

zbMATH Keywords

Hamiltonian cycle problemlongest cycle problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)