LINEAR-TIME COMPUTATION OF OPTIMAL SUBGRAPHS OF DECOMPOSABLE GRAPHS

被引：122

作者：

BERN, MW ^{[1
]}

LAWLER, EL ^{[1
]}

WONG, AL ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720

来源：

关键词：

D O I：

10.1016/0196-6774(87)90039-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：216 / 235

页数：20

共 23 条

[11] HOPCROFT JE, 1979, INTRO AUTOMATA THEOR, P65
[12] A LINEAR ALGORITHM FOR THE DOMINATION NUMBER OF A SERIES-PARALLEL GRAPH
KIKUNO, T
YOSHIDA, N
KAKUDA, Y
[J]. DISCRETE APPLIED MATHEMATICS, 1983, 5 (03) : 299 - 311
[13] ON THE ALGORITHMIC COMPLEXITY OF TOTAL DOMINATION
LASKAR, R
PFAFF, J
HEDETNIEMI, SM
HEDETNIEMI, ST
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03): : 420 - 425
[14] MITCHELL S, 1977, 8TH P SE C COMB GRAP, P489
[15] MONIEN D, 1981, 13TH P ANN S THEOR C, P207
[16] OPTIMUM DOMINATION IN WEIGHTED TREES
NATARAJAN, KS
WHITE, LJ
[J]. INFORMATION PROCESSING LETTERS, 1978, 7 (06) : 261 - 265
[17] Pfaff J., 1984, C NUMER, V45, P71
[18] PFAFF J, 1983, 428 CLEMS U TECH REP
[19] DYNAMIC-PROGRAMMING ALGORITHMS FOR RECOGNIZING SMALL-BANDWIDTH GRAPHS IN POLYNOMIAL-TIME
SAXE, JB
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (04): : 363 - 369
[20] LINEAR-TIME COMPUTABILITY OF COMBINATORIAL PROBLEMS ON SERIES-PARALLEL GRAPHS
TAKAMIZAWA, K
NISHIZEKI, T
SAITO, N
[J]. JOURNAL OF THE ACM, 1982, 29 (03) : 623 - 641