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:||https://doi.org/10.1007/978-3-642-02882-3_46|
|Record Created:||15 Dec 2009 10:35|
|Last Modified:||15 May 2017 16:04|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|