Planar multicommodity flows, max cut, and the Chinese Postman Problem. (English) Zbl 0747.05067
Polyhedral combinatorics, Proc. Workshop, Morristown/NJ (USA) 1989, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 1, 189-202 (1990).
Summary: [For the entire collection see Zbl 0722.00003.]
For planar graphs, Seymour proved that there is a multicommodity flow if and only if there is no negative cut. Matsumoto et al. have shown how to find the flow by solving \(O(n)\) matching problems in a graph with \(n\) nodes. Our aim is to point out that the flow can be found by solving a single Chinese Postman Problem in the dual graph and that the problem can be solved in \(O(n^{3/2}\log n)\) time. The same ideas apply to the max cut problem in planar graphs. We also give a simple algorithmic proof of Seymour’s theorem on \(T\)-joins.
For planar graphs, Seymour proved that there is a multicommodity flow if and only if there is no negative cut. Matsumoto et al. have shown how to find the flow by solving \(O(n)\) matching problems in a graph with \(n\) nodes. Our aim is to point out that the flow can be found by solving a single Chinese Postman Problem in the dual graph and that the problem can be solved in \(O(n^{3/2}\log n)\) time. The same ideas apply to the max cut problem in planar graphs. We also give a simple algorithmic proof of Seymour’s theorem on \(T\)-joins.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 94C15 | Applications of graph theory to circuits and networks |
| 05C38 | Paths and cycles |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
