Sublinear-Time Algorithms for Tournament Graphs

Dantchev, Stefan; Friedetzky, Tom; Nagel, Lars

doi:10.1007/978-3-642-02882-3_46

Sublinear-Time Algorithms for Tournament Graphs

Dantchev, Stefan; Friedetzky, Tom; Nagel, Lars

Authors

Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor

Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor

Lars Nagel

Contributors

H. Q. Ngo
Editor

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.

Citation

Dantchev, S., Friedetzky, T., & Nagel, L. (2009). Sublinear-Time Algorithms for Tournament Graphs. In H. Q. Ngo (Ed.), Computing and combinatorics : 15th Annual International Conference, COCOON 2009, 13-15 July 2009, Niagara Falls, NY, USA ; proceedings (459-471). https://doi.org/10.1007/978-3-642-02882-3_46

Conference Name	15th Annual International Conference of Computing and Combinatorics (COCOON 2009)
Conference Location	Niagara Falls, New York, USA
Start Date	Jul 13, 2009
End Date	Jul 15, 2009
Publication Date	Jul 1, 2009
Deposit Date	Dec 15, 2009
Pages	459-471
Series Title	Lecture notes in computer science
Series Number	5609
Series ISSN	0302-9743,1611-3349
Book Title	Computing and combinatorics : 15th Annual International Conference, COCOON 2009, 13-15 July 2009, Niagara Falls, NY, USA ; proceedings.
DOI	https://doi.org/10.1007/978-3-642-02882-3_46
Keywords	Sublinear-time algorithms, Tournament, Random walk.
Public URL	https://durham-repository.worktribe.com/output/1159629