AN O(N LOG2 N) ALGORITHM FOR MAXIMUM FLOW IN UNDIRECTED PLANAR NETWORKS

被引：43

作者：

HASSIN, R ^{[1
]}

JOHNSON, DB ^{[1
]}

机构：

[1] PENN STATE UNIV,DEPT COMP SCI,UNIVERSITY PK,PA 16802

来源：

关键词：

D O I：

10.1137/0214045

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：612 / 624

页数：13

共 13 条

[1]

Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[2]

Ford L.R., 1956, CAN J MATH, V8, P399, DOI [10.4153/CJM-1956-045-5, DOI 10.4153/CJM-1956-045-5]

[3]

Frederickson G. N., 1983, 24th Annual Symposium on Foundations of Computer Science, P242, DOI 10.1109/SFCS.1983.69

[4]

Galil Z., 1978, 19th Annual Symposium on Foundations of Computer Science, P231, DOI 10.1109/SFCS.1978.5

[5] MAXIMUM FLOW IN (S,T) PLANAR NETWORKS [J].

HASSIN, R .

[6]

Itai A., 1979, SIAM Journal on Computing, V8, P135, DOI 10.1137/0208012

[7]

Johnson D. B., 1982, 20TH P ANN ALL C COM, P898

[8] EFFICIENT ALGORITHMS FOR SHORTEST PATHS IN SPARSE NETWORKS [J].

JOHNSON, DB .

[9]

Lawler E.L., 1976, COMBINATORIAL OPTIMI

[10] GENERALIZED NESTED DISSECTION [J].

LIPTON, RJ ;

ROSE, DJ ;

TARJAN, RE .