Electric routing and concurrent flow cutting
arXiv:0909.2859
Abstract
We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the L1->L1 operator norm of the inverse graph Laplacian. We show how this norm reflects both latency and congestion of electric routing.
21 pages, 0 figures. To be published in Springer LNCS Book No. 5878, Proceedings of The 20th International Symposium on Algorithms and Computation (ISAAC'09)