@inproceedings { ,
title = {Sublinear-Time Algorithms for Tournament Graphs},
abstract = {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.},
conference = {15th Annual International Conference of Computing and Combinatorics (COCOON 2009)},
doi = {10.1007/978-3-642-02882-3\_46},
note = {EPrint Processing Status: Author unable to supply full text},
pages = {459-471},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1159629},
keyword = {Algorithms and Complexity in Durham (ACiD), Sublinear-time algorithms, Tournament, Random walk.},
year = {2009},
author = {Dantchev, Stefan and Friedetzky, Tom and Nagel, Lars}
editor = {Ngo, H. Q.}
}