Incremental All-Pairs Effective Resistance in Almost-Linear TimeResearch Paper
The effective resistance between two vertices of a graph with edge conductances is the energy of the electrical flow that sends one unit of current between them. More generally, a demand with zero sum has energy , where is the graph Laplacian. These quantities drive spectral sparsification (Spielman–Srivastava, SIAM…