pith. sign in

arxiv: 0909.2859 · v1 · submitted 2009-09-15 · 💻 cs.DM · cs.DC

Electric routing and concurrent flow cutting

Jonathan Kelner , Petar Maymounkov This is my paper
classification 💻 cs.DM cs.DC
keywords routingelectricflowgraphnormamenableboundchanges
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Flows in Almost Linear Time via Adaptive Preconditioning

    cs.DS 2019-06 unverdicted novelty 7.0

    Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.