On a simple randomized algorithm for finding a 2-factor in sparse graphs

DOI10.1016/j.ipl.2005.04.001zbMath1184.68623OpenAlexW2089653160MaRDI QIDQ1041775

Gopal Pandurangan

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.04.001

zbMATH Keywords

random walks2-factorHamiltonian cyclegraph algorithmsrandomized algorithmslong cyclesparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Approximating the Longest Cycle Problem in Sparse Graphs
• Finding paths and cycles of superpolylogarithmic length
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Finding hidden hamiltonian cycles
• Finding a Path of Superlogarithmic Length
• Stable networks and product graphs
• Automata, Languages and Programming

This page was built for publication: On a simple randomized algorithm for finding a 2-factor in sparse graphs