Maximum bipartite flow in networks with adaptive channel width

DOI10.1016/j.tcs.2010.10.023zbMath1218.68035OpenAlexW2064054678MaRDI QIDQ541660

Thomas Moscibroda, Aleksander Mądry, Aravind Srinivasan, Yossi Azar, Debmalya Panigrahi

Publication date: 7 June 2011

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

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

zbMATH Keywords

graph algorithmwireless networksmaximum flowadaptive channel widthlinear program rounding

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation algorithms for the unsplittable flow problem
• The hardness of approximation: Gap location
• Combinatorial algorithms for the unsplittable flow problem
• Beyond the flow decomposition barrier
• Maximal Flow Through a Network
• Random sampling in residual graphs
• A new approach to the maximum-flow problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Network Flow and Testing Graph Connectivity
• All-norm approximation algorithms
• Algorithm Theory - SWAT 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Maximum bipartite flow in networks with adaptive channel width