Electric routing and concurrent flow cutting

Jonathan Kelner; Petar Maymounkov

Electric routing and concurrent flow cutting

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 0909.2859 v1 pith:H5XUICYS submitted 2009-09-15 cs.DM cs.DC

Jonathan Kelner , Petar Maymounkov This is my paper · ORCID

classification cs.DMcs.DC

keywords routingelectricflowgraphnormamenableboundchanges

verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Flows in Almost Linear Time via Adaptive Preconditioning
cs.DS 2019-06 unverdicted novelty 7.0 of 10

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.

Pith tools