Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Finding Long Paths, Cycles and Circuits
verfasst von : Harold N. Gabow, Shuxin Nie
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a polynomial-time algorithm to find a cycle of length
$\exp(\Omega(\sqrt{\log \ell}))$
in an undirected graph having a cycle of length ≥ ℓ. This is a slight improvement over previously known bounds. In addition the algorithm is more general, since it can similarly approximate the longest circuit, as well as the longest
S
-circuit (i.e., for
S
an arbitrary subset of vertices, a circuit that can visit each vertex in
S
at most once). We also show that any algorithm for approximating the longest cycle can approximate the longest circuit, with a square root reduction in length. For digraphs, we show that the long cycle and long circuit problems have the same approximation ratio up to a constant factor. We also give an algorithm to find a
vw
-path of length ≥ log
n
/loglog
n
if one exists; this is within a loglog
n
factor of a hardness result.