On complexity, representation and approximation of integral multicommodity flows
From MaRDI portal
Publication:1962043
DOI10.1016/S0166-218X(99)00133-XzbMath0951.68048WikidataQ127374488 ScholiaQ127374488MaRDI QIDQ1962043
Anand Srivastav, Peter Stangier
Publication date: 18 December 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Fast approximation of minimum multicast congestion – Implementation VERSUS Theory ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Multicast Routing and Design of Sparse Connectors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Multicommodity flows in planar graphs
- Tight integral duality gap in the Chinese postman problem
- Geometric algorithms and combinatorial optimization
- An \(O(IVI^3)\) algorithm for finding maximum flows in networks
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- A linear-time algorithm for edge-disjoint paths in planar graphs
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- On the Complexity of Timetable and Multicommodity Flow Problems
This page was built for publication: On complexity, representation and approximation of integral multicommodity flows
