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

DOI10.1007/978-3-540-93980-1_1zbMATH Open1192.90231OpenAlexW1532118422MaRDI QIDQ3602825FDOQ3602825

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

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

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)