Electric routing and concurrent flow cutting

DOI10.1016/J.TCS.2010.06.013zbMATH Open1221.68172OpenAlexW2570775423MaRDI QIDQ553348FDOQ553348

Authors: Petar Maymounkov, Jonathan Kelner 

Publication date: 27 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.013

Recommendations

• Electric routing and concurrent flow cutting
• Localization of electrical flows
• Mixing times and \(\ell_p\) bounds for oblivious routing
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• A new approach to computing maximum flows using electrical flows

zbMATH Keywords

spectral graph theoryLaplacian operatoroblivious routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Internet topics (68M11)

Cites Work

• Approximate distance oracles
• Open problems of Paul Erd�s in graph theory
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compact name-independent routing with minimum stretch
• Title not available (Why is that?)
• New lower bounds for oblivious routing in undirected graphs
• Expanders via random spanning trees

Cited In (5)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Localization of electrical flows
• Electric routing and concurrent flow cutting
• Randomized oblivious integral routing for minimizing power cost
• Mixing times and \(\ell_p\) bounds for oblivious routing

This page was built for publication: Electric routing and concurrent flow cutting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553348)