Random Structures and Algorithms · 1995 · 197 citations · 14 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsProbability TheoryGraph TheoryProbabilistic CombinatoricsRandom WalksExpected-time AnalysisLower Bound ComputationLower Bound TechniquesRandom GraphsRandom Walk Cover TimeRandom Walks On GraphsRandomized Covering AlgorithmsRandomized Graph Algorithms
Abstract We prove that the expected time for a random walk to cover all n vertices of a graph is at least (1 + o (1)) n In n .
14
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations