Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
Lars Nagel
H. Q. Ngo
Editor
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.
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 |
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 |
Sherali-Adams and the binary encoding of combinatorial principles
(2020)
Presentation / Conference Contribution
Resolution and the binary encoding of combinatorial principles
(2019)
Presentation / Conference Contribution
Simplicial Complex Entropy
(2017)
Presentation / Conference Contribution
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
(2007)
Presentation / Conference Contribution
Parameterized proof complexity
(2007)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search