Paper Info
Title
Sublinear-time algorithms for tournament graphs
Abstract
We show that a random walk on a tournament on n vertices finds either a sink or a 3-cycle in expected time O √ n · log n · log ∗ n , that is, sublinear both in the size of the description of the graph as well as in the number of vertices. This result is motivated by the search of a generic algorithm for solving a large class of search problems called Local Search, LS. LS is defined by us as a generalisation of the well-known class PLS.
Year
DOI
Venue
2011
10.1007/s10878-010-9325-7
Computing and Combinatorics
Keywords
DocType
Volume
random walk,tournament graph,sublinear-time algorithm,n vertex,expected time,sublinear-time algorithms · tournament · random walk,log n
Journal
22
Issue
ISSN
Citations 
3
1382-6905
0
PageRank 
References 
Authors
0.34
3
3
Name
Order
Citations
PageRank
Stefan Dantchev1282.77
tom friedetzky224924.47
Lars Nagel37613.58