LINEAR TIME ALGORITHMS FOR NP-HARD PROBLEMS RESTRICTED TO PARTIAL K-TREES

被引：339

作者：

ARNBORG, S ^{[1
]}

PROSKUROWSKI, A ^{[1
]}

机构：

[1] UNIV OREGON,DEPT COMP & INFORMAT SCI,EUGENE,OR 97403

来源：

关键词：

D O I：

10.1016/0166-218X(89)90031-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

引用

页码：11 / 24

页数：14

共 21 条

[1] REDUCED STATE ENUMERATION - ANOTHER ALGORITHM FOR RELIABILITY EVALUATION
ARNBORG, S
[J]. IEEE TRANSACTIONS ON RELIABILITY, 1978, 27 (02) : 101 - 105
[2] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES
ARNBORG, S
PROSKUROWSKI, A
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02): : 305 - 314
[3] ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985
[4] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE
ARNBORG, S
CORNEIL, DG
PROSKUROWSKI, A
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02): : 277 - 284
[5] LINEAR-TIME COMPUTATION OF OPTIMAL SUBGRAPHS OF DECOMPOSABLE GRAPHS
BERN, MW
LAWLER, EL
WONG, AL
[J]. JOURNAL OF ALGORITHMS, 1987, 8 (02) : 216 - 235
[6] Bertele Umberto, 1972, NONSERIAL DYNAMIC PR
[7] COMPLEMENT REDUCIBLE GRAPHS
CORNEIL, DG
LERCHS, H
BURLINGHAM, LS
[J]. DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) : 163 - 174
[8] A DYNAMIC-PROGRAMMING APPROACH TO THE DOMINATING SET PROBLEM ON KAPPA-TREES
CORNEIL, DG
KEIL, JM
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (04): : 535 - 543
[9] Garey M. R., 1979, COMPUTERS INTRACTABI
[10] Gavril F., 1972, SIAM Journal on Computing, V1, P180, DOI 10.1137/0201013