THE ALL-PAIRS MIN CUT PROBLEM AND THE MINIMUM CYCLE BASIS PROBLEM ON PLANAR GRAPHS

被引：33

作者：

HARTVIGSEN, D ^{[1
]}

MARDON, R ^{[1
]}

机构：

[1] FLORIDA AGCY HLTH CARE ADM,TALLAHASSEE,FL 32303

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 03期

关键词：

NETWORKS FLOWS; MIN CUTS; CYCLE BASES; GRAPH THEORY;

D O I：

10.1137/S0895480190177042

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The all-pairs min cut (APMC) problem on a nonnegative weighted graph is the problem of finding, for every pair of nodes, the min cut separating the pair. It is shown that on planar graphs, the APMC problem is equivalent to another problem, the minimum cycle basis (MCB) problem, on the dual graph. This is shown by characterizing the structure of MCBs on planar graphs in several ways. This leads to a new algorithm for solving both of these problems on planar graphs. The complexity of this algorithm equals that of the best algorithm for either problem, but is simpler.

引用

页码：403 / 418

页数：16

共 29 条

[11]

Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955

[12]

FREDERICKSON GN, 1987, SIAM J COMPUT, V16, P1004, DOI 10.1137/0216064

[13] MULTI-TERMINAL NETWORK FLOWS [J].