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

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

Mathematics Subject Classification ID

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

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

(22)

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

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)