Approximating the longest cycle problem on graphs with bounded degree

DOI10.1007/11533719_88MaRDI QIDQ5717010zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Xingxing Yu, Wenan Zang, Zhicheng Gao

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11533719

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Approximating Longest Cycles in Graphs with Bounded Degrees
• Circumference of Graphs with Bounded Degree
• scientific article; zbMATH DE number 426167
• Finding Paths and Cycles of Superpolylogarithmic Length
• Approximating the Longest Cycle Problem in Sparse Graphs

Cited in

(14)

• On the Cycle Augmentation Problem: hardness and approximation algorithms
• The longest cycle problem is polynomial on interval graphs
• The upper bound on the Eulerian recurrent lengths of complete graphs obtained by an IP solver
• An approximation algorithm for the longest cycle problem in solid grid graphs
• The NPO-completeness of the longest Hamiltonian cycle problem
• Approximating the Longest Cycle Problem in Sparse Graphs
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Circumference of Graphs with Bounded Degree
• Going far from degeneracy
• Going far from degeneracy
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Longest cycle above Erdős-Gallai bound
• Finding the longest isometric cycle in a graph

This page was built for publication: Approximating the longest cycle problem on graphs with bounded degree

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