Breadth-first search on a Ramanujan graph

08/26/2019
by   Janko Boehm, et al.
0

The behavior of the randomized breadth-first search algorithm is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the expander mixing lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maximize the spectral gap. We compare our theoretical results with computational experiments on flip graphs of point configurations. The latter is relevant for enumerating triangulations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset