|
|||||
|
|
Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs |
|
| Authors: | Frieda Granot Michal Penn |
| Institution: | a Faculty of Commerce and Business Administration, The University of British Columbia, Vancouver, BC, Canada V6T 1Z2 b Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Haifa, Israel 32000 |
| Abstract: | In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST2-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST2-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST2-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one. |
| Keywords: | Planar graphs Vertex and edge capacitated Two-flow Integral Algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |