We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

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:19 Mar 2010 16:39

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