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).

Related: A follow-up work by Yaniv Sabo (MSc, TAU, Nov 2016).

Back to Oded Goldreich's homepage.