Sublinear‐time algorithms for tournament graphs

0.00 Avg rating—0 Votes

Article ID:	iaor20119248
Volume:	22
Issue:	3
Start Page Number:	469
End Page Number:	481
Publication Date:	Oct 2011
Journal:	Journal of Combinatorial Optimization
Authors:	Dantchev Stefan, Friedetzky Tom, Nagel Lars
Keywords:	heuristics

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 (\sqrt{n} \log n \sqrt{\log^{*} n})$ equ1 , that is, sublinear both in the size of the description of the graph as well as in the number of vertices.

Reviews

Required fields are marked *. Your email address will not be published.