Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

DOI10.1137/0215034MaRDI QIDQ3720621zbMATH OpenOpenAlexFDO

Authors Kazuhiko Matsumoto, Nobuji Saito, Takao Nishizeki

Publication date 1986

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

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

zbMATH Keywords

cut conditionmax flow-min cut theoremminimum cycleplanarplanar graphseparator theoremweighted matching

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Recommendations

• scientific article; zbMATH DE number 16725
• Multicommodity flows in certain planar directed networks
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Algorithms for multicommodity flows in planar graphs
• Flow in Planar Graphs with Multiple Sources and Sinks

Cited in

(12)

• Undirected distances and the postman-structure of graphs
• Algorithms for multicommodity flows in planar graphs
• An algorithm for min-cost edge-disjoint cycles and its applications
• Parity conditions in homotopic knock-knee routing
• On local routing of two-terminal nets
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• On multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• scientific article; zbMATH DE number 16725 (Why is no real title available?)
• Cyclically monotone non-optimal N-marginal transport plans and Smirnov-type decompositions for N-flows
• Finding edge-disjoint paths in partial k-trees
• Multicommodity flows in certain planar directed networks

This page was built for publication: Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

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