SPARSEST CUTS AND BOTTLENECKS IN GRAPHS

被引：55

作者：

MATULA, DW ^{[1
]}

SHAHROKHI, F ^{[1
]}

机构：

[1] UNIV N TEXAS,DEPT COMP SCI,DENTON,TX 76203

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 27卷 / 1-2期

关键词：

D O I：

10.1016/0166-218X(90)90133-W

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The problem of determining a sparsest cut in a graph is characterized and its computation shown to be NP-hard. A class of sparsest cuts, termed bottlenecks, is characterized by a dual relation to a particular polynomial time computable multicommodity flow problem. Efficient computational techniques for determining bottlenecks in a broad class of instances are presented. © 1990.

引用

页码：113 / 123

页数：11

共 13 条

[1] BIANCHINI RP, 1987, IEEE T COMPUT, V36, P396, DOI 10.1109/TC.1987.1676922
[2] BISWAS J, 1986, P IEEE FALL JOINT CO, P629
[3] Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955
[4] Frederickson G. N., 1983, 24th Annual Symposium on Foundations of Computer Science, P242, DOI 10.1109/SFCS.1983.69
[5] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[6] Gerla M., 1974, P NAT TEL C SAN DIEG, P1074
[7] AN EFFICIENT ALGORITHM FOR FINDING MULTICOMMODITY FLOWS IN PLANAR NETWORKS
MATSUMOTO, K
NISHIZEKI, T
SAITO, N
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (02) : 289 - 302
[8] Matula D. W., 1985, GRAPH THEORY ITS APP, P543
[9] MATULA DW, 1986, CLASSIFICATION TOOL, P289
[10] MATULA DW, 1983, NUMERICAL TAXONOMY, V1, P156

← 1 2 →