Approximating the Longest Cycle Problem in Sparse Graphs

DOI10.1137/S0097539701395486zbMath1041.68069OpenAlexW2028363565MaRDI QIDQ3149885

Carlos Subi, Rajeev Motwani, Tomás Feder

Publication date: 29 September 2002

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

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

zbMATH Keywords

approximation algorithmsHamiltonian graphslong paths and cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (9)

Spotting Trees with Few Leaves ⋮ Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ 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 ⋮ Finding large cycles in Hamiltonian graphs ⋮ Approximating the longest paths in grid graphs ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs

This page was built for publication: Approximating the Longest Cycle Problem in Sparse Graphs