On complexity, representation and approximation of integral multicommodity flows

DOI10.1016/S0166-218X(99)00133-XMaRDI QIDQ1962043zbMATHWikidataFDO

Authors Anand Srivastav, Peter Stangier

Publication date 18 December 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

integral multicommodity flow problems

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 852056 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Geometric algorithms and combinatorial optimization
• Multicommodity flows in planar graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Tight integral duality gap in the Chinese postman problem

Cited in

(14)

• Flows with unit path capacities and related packing and covering problems
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• Minimal multicut and maximal integer multiflow: a survey
• Integer multicommodity flow 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
• Integral polyhedra related to integer multicommodity flows on a cycle
• Multicast Routing and Design of Sparse Connectors
• On fractional multicommodity flows and distance functions
• scientific article; zbMATH DE number 840702 (Why is no real title available?)
• Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
• Multicommodity flow in trees: packing via covering and iterated relaxation
• scientific article; zbMATH DE number 4139464 (Why is no real title available?)

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)