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

DOI10.1007/978-3-540-93980-1_1zbMath1192.90231OpenAlexW1532118422MaRDI QIDQ3602825

No author found.

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

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

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• A polynomial algorithm for b-matchings: An alternative approach
• Conversion of coloring algorithms into maximum weight independent set algorithms
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the disjoint paths problem
• The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
• Survivable network design with degree or order constraints
• Approximating minimum bounded degree spanning trees to within one of optimal
• Multicommodity demand flow in a tree and packing integer programs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• The Demand-Matching Problem

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