Finding Cycles and Trees in Sublinear Time

Artur Czumaj, Oded Goldreich, Dana Ron +3

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\ge 3$ and tree-minors in bounded-degree graphs. The complexity of these algorithm…