An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

DOI10.1137/0214023zbMath0572.90027OpenAlexW1989626562MaRDI QIDQ3690541

Nobuji Saito, Kazuhiko Matsumoto, Takao Nishizeki

Publication date: 1985

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

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

zbMATH Keywords

algorithmpolynomial timecut-conditionmax flow-min cut theoremmulticommodity flows in planar graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (12)

Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly ⋮ Algorithms for multicommodity flows in planar graphs ⋮ Online interval scheduling with predictions ⋮ Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ Finding edge-disjoint paths in partial k-trees ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Multicommodity flows in certain planar directed networks ⋮ Fast and efficient solution of path algebra problems ⋮ A linear-time algorithm for edge-disjoint paths in planar graphs ⋮ A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works ⋮ Sparsest cuts and bottlenecks in graphs

This page was built for publication: An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks