On complexity, representation and approximation of integral multicommodity flows
DOI10.1016/S0166-218X(99)00133-XzbMATH Open0951.68048WikidataQ127374488 ScholiaQ127374488MaRDI QIDQ1962043FDOQ1962043
Authors: Anand Srivastav, Peter Stangier 
Publication date: 18 December 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
- Integer plane multiflows with a mixed number of demands
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Fast approximation algorithms for multicommodity flow problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Title not available (Why is that?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Title not available (Why is that?)
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- A linear-time algorithm for edge-disjoint paths in planar graphs
- Multicommodity flows in planar graphs
- An \(O(IVI^3)\) algorithm for finding maximum flows in networks
- Tight integral duality gap in the Chinese postman problem
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- Title not available (Why is that?)
Cited In (12)
- Integral polyhedra related to integer multicommodity flows on a cycle
- Minimal multicut and maximal integer multiflow: a survey
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- Multicast Routing and Design of Sparse Connectors
- Title not available (Why is that?)
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Flows with unit path capacities and related packing and covering problems
- A fixed-parameter tractability result for multicommodity demand flow in trees
- Express analysis and aggregated representation of the set of reachable flows for a multicommodity network system
- Title not available (Why is that?)
- Integer multicommodity flow problems
- On fractional multicommodity flows and distance functions
This page was built for publication: On complexity, representation and approximation of integral multicommodity flows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962043)
