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 [J].

ARNBORG, S .

IEEE TRANSACTIONS ON RELIABILITY, 1978, 27 (02) :101-105

[2] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

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 [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

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 [J].

FARLEY, AM ;

PROSKUROWSKI, A .

NETWORKS, 1982, 12 (04) :393-403

[8] NETWORKS IMMUNE TO ISOLATED FAILURES [J].

FARLEY, AM .

NETWORKS, 1981, 11 (03) :255-268

[9]

NEUFELD EM, 1983, TR837 U SASK DEP COM

[10] SEPARATING SUBGRAPHS IN K-TREES - CABLES AND CATERPILLARS [J].

PROSKUROWSKI, A .

DISCRETE MATHEMATICS, 1984, 49 (03) :275-285

← 1 2 →