  The total effective resistance, also called the Kirchhoff index, provides a
robustness measure for a graph $G$. We consider two optimization problems of
adding $k$ new edges to $G$ such that the resulting graph has minimal total
effective resistance (i.e., is most robust) -- one where the new edges can be
anywhere in the graph and one where the new edges need to be incident to a
specified focus node. The total effective resistance and effective resistances
between nodes can be computed using the pseudoinverse of the graph Laplacian.
The pseudoinverse may be computed explicitly via pseudoinversion; yet, this
takes cubic time in practice and quadratic space. We instead exploit
combinatorial and algebraic connections to speed up gain computations in an
established generic greedy heuristic. Moreover, we leverage existing randomized
techniques to boost the performance of our approaches by introducing a
sub-sampling step. Our different graph- and matrix-based approaches are indeed
significantly faster than the state-of-the-art greedy algorithm, while their
quality remains reasonably high and is often quite close. Our experiments show
that we can now process larger graphs for which the application of the
state-of-the-art greedy approach was impractical before.
