We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Sublinear-time algorithms for tournament graphs.

Dantchev, Stefan and Friedetzky, Tom and Nagel, Lars (2009) 'Sublinear-time algorithms for tournament graphs.', in Computing and combinatorics : 15th Annual International Conference, COCOON 2009, 13-15 July 2009, Niagara Falls, NY, USA ; proceedings. Berlin: Springer, pp. 459-471. Lecture notes in computer science. (5609).


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.

Item Type:Book chapter
Keywords:Sublinear-time algorithms, Tournament, Random walk.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar