Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331339 | Information Processing Letters | 2005 | 7 Pages |
Abstract
We analyze the performance of a simple randomized algorithm for finding 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of degree at most three. For the directed case, the algorithm finds a 2-factor in O(n2) expected time. The analysis of our algorithm is based on random walks on the line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [On selecting a satisfying truth assignment, in: Proc. 32nd Annual IEEE Symp. on the Foundations of Computer Science (FOCS), 1991, p. 163]. For the undirected case, the algorithm finds a 2-factor in O(n3) expected time. We also analyze random versions of these graphs and show that cycles of length Ω(n/logn) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [Finding hidden Hamilton cycles, Random Structures Algorithms 5 (1994) 395] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [On approximating the longest path in a graph, Algorithmica 18 (1997) 82].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gopal Pandurangan,