New answers tagged pr.probability
1
If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time $\widetilde{O}(m)$. This is done explicitly in this paper by Spielman and Srivastava, Theorem 2.
My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.
Top 50 recent answers are included
