On a simple randomized algorithm for finding a 2-factor in sparse graphs |
| |
Authors: | Gopal Pandurangan |
| |
Affiliation: | Department of Computer Science, Purdue University, 250 N. Univ. St., West Lafayette, IN 47907, USA |
| |
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: | Graph algorithms Randomized algorithms Random walks Sparse graphs 2-factor Hamiltonian cycle Long cycle |
本文献已被 ScienceDirect 等数据库收录! |
|