Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
From MaRDI portal
Publication:3720621
DOI10.1137/0215034zbMath0592.05024MaRDI 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
planar; planar graph; cut condition; weighted matching; separator theorem; max flow-min cut theorem; minimum cycle
68Q25: Analysis of algorithms and problem complexity
90B10: Deterministic network models in operations research
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
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