Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

DOI10.1137/0215034zbMath0592.05024OpenAlexW2008162025MaRDI QIDQ3720621

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

planarplanar graphcut conditionweighted matchingseparator theoremmax flow-min cut theoremminimum cycle

Mathematics Subject Classification ID

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

Related Items (6)

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

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