Minimizing Effective Resistance of a Graph

SIAM Review, problems and techniques section, 50(1):37-66, February 2008.
Shorter version appeared in Proceedings of the 17th International Symposium on the Mathematical Theory of Networks and Systems, pages 185-1196, July 2006, Kyoto.

• eff_res.pdf

• eff_res_mtns06.pdf

The effective resistance between two nodes of a weighted graph is the electrical resistance seen between the nodes of a resistor network with branch conductances given by the edge weights. The effective resistance comes up in many applications and fields in addition to electrical network analysis, including, for example, Markov chains and continuous-time averaging networks. In this paper we study the problem of allocating edge weights on a given graph in order to minimize the total effective resistance, i.e., the sum of the resistances between all pairs of nodes. We show that this is a convex optimization problem, and can be solved efficiently either numerically, or, in some cases, analytically. We show that optimal allocation of the edge weights can reduce the total effective resistance of the graph (compared to uniform weights) by a factor that grows unboundedly with the size of the graph. We show that among all graphs with n nodes, the path has the largest value of optimal total effective resistance, and the complete graph the least.