The maximum concurrent flow problem
From MaRDI portal
Publication:3474283
DOI10.1145/77600.77620zbMath0696.68071OpenAlexW2035652501WikidataQ56030328 ScholiaQ56030328MaRDI QIDQ3474283
Farhad Shahrokhi, David W. Matula
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/77600.77620
network partitioninggraph algorithmsroutingmulticommodity flowpolynomial-time approximation schemeprimal-dual algorithmsmaximum concurrent flowpath and circuit problems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items (56)
Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Dynamic maintenance of majority information in constant time per update ⋮ A provably tight delay-driven concurrently congestion mitigating global routing algorithm ⋮ A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ Vertical perimeter versus horizontal perimeter ⋮ An interior-point approach for primal block-angular problems ⋮ EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS ⋮ Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow ⋮ A simple method for convex optimization in the oracle model ⋮ A network flow model of group technology ⋮ Drawings of graphs on surfaces with few crossings ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ A combinatorial approximation algorithm for supply chain network flow problem ⋮ The permutation-path coloring problem on trees. ⋮ Multi-core processor scheduling with respect to data bus bandwidth ⋮ On Canonical Concurrent Flows, Crossing Number and Graph Expansion ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ Concurrent flows and packet routing in Cayley graphs (Preliminary version) ⋮ Dynamic reversible lane optimization in autonomous driving environments: balancing efficiency and safety ⋮ Barrier subgradient method ⋮ Euclidean distortion and the sparsest cut ⋮ Unnamed Item ⋮ A fast polynomial time algorithm for logistics network flows ⋮ Sparsest cuts and concurrent flows in product graphs. ⋮ Fast approximation of minimum multicast congestion – Implementation VERSUS Theory ⋮ An exact approach for the maximum concurrent \(k\)-splittable flow problem ⋮ Prolong the Lifetime of Wireless Sensor Networks Through Mobility: A General Optimization Framework ⋮ Lexicographic maximin optimisation for fair bandwidth allocation in computer networks ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ Ancestor tree for arbitrary multi-terminal cut functions ⋮ Polynomiality of sparsest cuts with fixed number of sources ⋮ Maximum concurrent flows and minimum cuts ⋮ On the complexity of bandwidth allocation in radio networks ⋮ A linear time algorithm for graph partition problems ⋮ A natural randomization strategy for multicommodity flow and related algorithms ⋮ Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem ⋮ From the physics of interacting polymers to optimizing routes on the London Underground ⋮ Faster min-max resource sharing in theory and practice ⋮ Unnamed Item ⋮ Exponential penalty function control of loss networks ⋮ A combinatorial approximation algorithm for concurrent flow problem and its application ⋮ Self-concordant barriers for convex approximations of structured convex sets ⋮ Optimization with additional variables and constraints ⋮ Upper bound of network capacity and a static optimal packet routing strategy ⋮ k -Splittable delay constrained routing problem: A branch-and-price approach ⋮ On max-\(k\)-sums ⋮ Flows on measurable spaces ⋮ Multicast Routing and Design of Sparse Connectors ⋮ Path optimization for graph partitioning problems ⋮ Flows with unit path capacities and related packing and covering problems ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Optimal flow and capacity allocation in multiple joint quickest paths of directed networks ⋮ Sparsest cuts and bottlenecks in graphs ⋮ Improving an interior-point approach for large block-angular problems by hybrid preconditioners ⋮ GMA: a Pareto optimal distributed resource-allocation algorithm
This page was built for publication: The maximum concurrent flow problem
