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

MTNS 2006 Paper Abstract

Close

Paper TuP12.2

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 June 23, 2024

Keywords Convex optimization, Networks and circuits, Systems on graphs

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.