Faster Walks in Graphs: A $\tilde{O}(n^2)$ Time-Space Trade-off for Undirected s-t Connectivity

Adrian Kosowski

In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the $S$-$T$-connectivity problem in undirected graphs (USTCON).…