## Aviv Reznik

## Abstract of Master Thesis (Weizmann Inst., 2011)

### Finding $k$-paths in cycle-free graph

In this thesis, we present two sub-linear time algorithms for finding paths
of length $k$ in bounded-degree cycle-free graphs. The complexity of our
algorithms is polynomially related to $k$, the degree bound, and the
distance of the graph from being $k$-path free (i.e. having no simple paths
of length $k$), denoted $\epsilon$. This improves over the known upper
bound of $O(\frac{k \cdot d^k}{\epsilon})$ for the cycle-free special case.

*Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, December 2011.*

Available:
the
thesis (in PDF file).

Back to Oded Goldreich's homepage.