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