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

DOI10.1137/130932326zbMATH Open1392.05050OpenAlexW2884345726MaRDI QIDQ4577772FDOQ4577772

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

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

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)

Cites Work

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

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)