All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs

DOI10.1137/130932326zbMath1392.05050OpenAlexW2884345726MaRDI QIDQ4577772

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

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

Related Items (4)

On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Packing non-zero \(A\)-paths in group-labelled graphs
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• Multicommodity flows in planar graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• Routing in Undirected Graphs with Constant Congestion
• The All-or-Nothing Multicommodity Flow Problem
• Edge-disjoint paths in Planar graphs with constant congestion
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• An Improved Algorithm for the Half-Disjoint Paths Problem
• Multicommodity demand flow in a tree and packing integer programs
• On the Complexity of Timetable and Multicommodity Flow Problems
• New hardness results for routing on disjoint paths
• Edge-Disjoint Paths in Planar Graphs with Constant Congestion
• On Approximating Node-Disjoint Paths in Grids
• Improved approximation for node-disjoint paths in planar graphs
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs