Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

DOI10.1007/978-3-540-93980-1_1MaRDI QIDQ3602825zbMATH OpenOpenAlexFDO

Authors

Publication date 12 February 2009

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-93980-1_1

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Multicommodity flow in trees: packing via covering and iterated relaxation
• Primal-dual approximation algorithms for integral flow and multicut in trees
• scientific article; zbMATH DE number 2038727
• scientific article; zbMATH DE number 6861995
• On complexity, representation and approximation of integral multicommodity flows

Cites work

• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A polynomial algorithm for b-matchings: An alternative approach
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the smallest k-edge connected spanning subgraph by LP-rounding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Conversion of coloring algorithms into maximum weight independent set algorithms
• scientific article; zbMATH DE number 5764784 (Why is no real title available?)
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• scientific article; zbMATH DE number 5485591 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Multicommodity demand flow in a tree and packing integer programs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the disjoint paths problem
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Survivable network design with degree or order constraints
• The Demand-Matching Problem
• The maximum edge-disjoint paths problem in bidirected trees

Cited in

(2)

• Multicommodity flow in trees: packing via covering and iterated relaxation
• Approximability of sparse integer programs

This page was built for publication: Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602825)