FORBIDDEN MINORS CHARACTERIZATION OF PARTIAL 3-TREES

被引：65

作者：

ARNBORG, S ^{[1
]}

PROSKUROWSKI, A ^{[1
]}

CORNEIL, DG ^{[1
]}

机构：

[1] UNIV TORONTO,DEPT COMP SCI,TORONTO M5S 1A4,ONTARIO,CANADA

来源：

DISCRETE MATHEMATICS | 1990年 / 80卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0012-365X(90)90292-P

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A k-tree is formed from a k-complete graph by recursively adding a vertex adjacent to all vertices in an existing k-complete subgraph. The many applications of partial k-trees (subgraphs of k-trees) have motivated their study from both the algorithmic and theoretical points of view. In this paper we characterize the class of partial 3-trees by its set of four minimal forbidden minors (H is a minor of G if H can be obtained from G by a finite sequence of edge-extraction and edge-contradiction operations.). © 1990.

引用

页码：1 / 19

页数：19

共 12 条

[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] ARNBORG S, 1984, IN PRESS DISCR APPL
[6] COLBOURN CJ, 1984, SPRINGER VERLAG LNCS, P128
[7] NETWORKS IMMUNE TO ISOLATED LINE FAILURES
FARLEY, AM
PROSKUROWSKI, A
[J]. NETWORKS, 1982, 12 (04) : 393 - 403
[8] NETWORKS IMMUNE TO ISOLATED FAILURES
FARLEY, AM
[J]. NETWORKS, 1981, 11 (03) : 255 - 268
[9] NEUFELD EM, 1983, TR837 U SASK DEP COM
[10] SEPARATING SUBGRAPHS IN K-TREES - CABLES AND CATERPILLARS
PROSKUROWSKI, A
[J]. DISCRETE MATHEMATICS, 1984, 49 (03) : 275 - 285

← 1 2 →