Sublinear-Time Algorithms for Tournament Graphs
(2009)
Presentation / Conference Contribution
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
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... Read More about Sublinear-Time Algorithms for Tournament Graphs.