Sublinear-Time Algorithms for Tournament Graphs

Dantchev, Stefan; Friedetzky, Tom; Nagel, Lars

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, July). Sublinear-Time Algorithms for Tournament Graphs. Presented at 15th Annual International Conference of Computing and Combinatorics (COCOON 2009), Niagara Falls, New York, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 15th Annual International Conference of Computing and Combinatorics (COCOON 2009)
• Start Date: Jul 13, 2009
• End Date: Jul 15, 2009
• Publication Date: Jul 1, 2009
• Deposit Date: Dec 15, 2009
• Print ISSN: 0302-9743
• 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