Testing Connectedness and Edge Connectedness

Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1

We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that $\epsilon$-tes…