All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs

DOI10.1137/130932326MaRDI QIDQ4577772zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date 3 August 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/130932326

zbMATH Keywords

approximation algorithmedge-disjoint pathsall-or-nothing multicommodity flow

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)

Recommendations

• The all-or-nothing multicommodity flow problem
• Edge-disjoint paths in planar graphs with constant congestion
• Edge-disjoint paths in planar graphs with constant congestion
• The all-or-nothing multicommodity flow problem
• On complexity, representation and approximation of integral multicommodity flows

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 5764892 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• An improved algorithm for the half-disjoint paths problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge-disjoint paths in planar graphs with constant congestion
• Edge-disjoint paths in planar graphs with constant congestion
• Graph minors. XIII: The disjoint paths problem
• Improved approximation for node-disjoint paths in planar graphs
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Multicommodity demand flow in a tree and packing integer programs
• Multicommodity flows in planar graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New hardness results for routing on disjoint paths
• On approximating node-disjoint paths in grids
• On the Complexity of Timetable and Multicommodity Flow Problems
• Packing non-zero \(A\)-paths in group-labelled graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Routing in undirected graphs with constant congestion
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• The all-or-nothing multicommodity flow problem
• The disjoint paths problem in quadratic time

Cited in

(10)

• The all-or-nothing multicommodity flow problem
• Edge-disjoint paths in planar graphs with constant congestion
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• Edge-disjoint paths in planar graphs with constant congestion
• On complexity, representation and approximation of integral multicommodity flows
• Maximum edge-disjoint paths in planar graphs with congestion 2
• The all-or-nothing multicommodity flow problem
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms

This page was built for publication: All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs

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