Journal
SIAM REVIEW
Volume 50, Issue 1, Pages 37-66Publisher
SIAM PUBLICATIONS
DOI: 10.1137/050645452
Keywords
weighted Laplacian eigenvalues; electrical network; weighted graph
Categories
Ask authors/readers for more resources
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 has the least.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available