Approximating Longest Cycles in Graphs with Bounded Degrees

DOI10.1137/050633263zbMath1118.05047OpenAlexW1993042687MaRDI QIDQ3446811

Wenan Zang, Xingxing Yu, Guantao Chen, Zhi-Cheng Gao

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050633263

zbMATH Keywords

algorithmlong cyclesbounded degree3-connected components

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Strong conflict-free coloring for intervals ⋮ Finding large cycles in Hamiltonian graphs ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Approximating the longest paths in grid graphs ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor

This page was built for publication: Approximating Longest Cycles in Graphs with Bounded Degrees