Ghosh, Arpita (Stanford Univ.), Boyd, Stephen (Stanford Univ.), Saberi, Amin (Stanford Univ.)

Minimizing Effective Resistance of a Graph

Scheduled for presentation during the Regular Session "Optimization" (TuP12), Tuesday, July 25, 2006, 15:45−16:10, Room 104b

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 8, 2024

Abstract

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. 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.