An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

DOI10.1137/0214023MaRDI QIDQ3690541zbMATH OpenOpenAlexFDO

Authors Kazuhiko Matsumoto, Nobuji Saito, 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

algorithmcut-conditionmax flow-min cut theoremmulticommodity flows in planar graphspolynomial time

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for multicommodity flows in planar graphs
• On multicommodity flows in planar graphs
• Flow in Planar Graphs with Multiple Sources and Sinks
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• An O(n\log ^2 n) Algorithm for Maximum Flow in Undirected Planar Networks

Cited in

(25)

• Algorithms for multicommodity flows in planar graphs
• A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Integer plane multiflows with a mixed number of demands
• Fast and efficient solution of path algebra problems
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly
• A combinatorial algorithm for the planar multiflow problem with demands located on three holes
• On multicommodity flows in planar graphs
• An Algorithm for the Maximal Multicommodity Funnel-Node Flow in an Undirected Network
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• scientific article; zbMATH DE number 16725 (Why is no real title available?)
• scientific article; zbMATH DE number 508828 (Why is no real title available?)
• Flow in Planar Graphs with Multiple Sources and Sinks
• Refined vertex sparsifiers of planar graphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Integer multiflows in acyclic planar digraphs
• Online interval scheduling with predictions
• Finding edge-disjoint paths in partial k-trees
• A face cover perspective to _1 embeddings of planar graphs
• A polynomial time algorithm for Steiner tree when terminals avoid a rooted K₄-minor
• Online interval scheduling with predictions
• Multicommodity flows in certain planar directed networks
• Sparsest cuts and bottlenecks in graphs
• Edge-disjoint paths in a grid bounded by two nested rectangles

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

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