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:
Record Created:15 Dec 2009 10:35
Last Modified:15 May 2017 16:04

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library