Multicommodity flows in planar graphs

DOI10.1016/S0095-8956(81)80012-3zbMath0465.90029MaRDI QIDQ1154916

Haruko Okamura, P. D. Seymour

Publication date: 1981

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

planar graph; multicommodity flows

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

90B10: Deterministic network models in operations research

Related Items

On Canonical Concurrent Flows, Crossing Number and Graph Expansion, Improved approximations for the minimum-cut ratio and the flux, On obstructions to small face covers in planar graphs, Parity conditions in homotopic knock-knee routing, Algorithms for routing around a rectangle, On local routing of two-terminal nets, Approximations for the disjoint paths problem in high-diameter planar networks, Switchbox routing in VLSI design: Closing the complexity gap, A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works, Routings for involutions of a hypercube, Projections of the capacitated network loading problem, A linear-time algorithm for edge-disjoint paths in planar graphs, Half-integral flows in a planar graph with four holes, NP-completeness of some edge-disjoint paths problems, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Optimum path packing on wheels: The consecutive case, On complexity, representation and approximation of integral multicommodity flows