THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .3. TREE-DECOMPOSITIONS, MINORS AND COMPLEXITY ISSUES

被引：120

作者：

COURCELLE, B

机构：

来源：

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 1992年 / 26卷 / 03期

关键词：

D O I：

10.1051/ita/1992260302571

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We relate the tree-decompositions of hypergraphs introduced by Robertson and Seymour to the finite and infinite algebraic expressions introduced by Bauderon and Courcelle. We express minor inclusion in monadic second-order logic, and we obtain grammatical characterizations of certain sets of graphs defined by excluded minors. We show how tree-decompositions can be used to construct quadratic algorithms deciding monadic second-order properties on hypergraphs of bounded tree-width.

引用

页码：257 / 286

页数：30

共 38 条

[1] FORBIDDEN MINORS CHARACTERIZATION OF PARTIAL 3-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A ;

CORNEIL, DG .

DISCRETE MATHEMATICS, 1990, 80 (01) :1-19

[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] EASY PROBLEMS FOR TREE-DECOMPOSABLE GRAPHS [J].

ARNBORG, S ;

LAGERGREN, J ;

SEESE, D .

JOURNAL OF ALGORITHMS, 1991, 12 (02) :308-340

[4]

ARNBORG S, 1991, LECT NOTES COMPUT SC, V532, P70, DOI 10.1007/BFb0017382

[5] 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

[6] INFINITE HYPERGRAPHS .1. BASIC PROPERTIES [J].

BAUDERON, M .

THEORETICAL COMPUTER SCIENCE, 1991, 82 (02) :177-214

[7] GRAPH EXPRESSIONS AND GRAPH REWRITINGS [J].

BAUDERON, M ;

COURCELLE, B .

MATHEMATICAL SYSTEMS THEORY, 1987, 20 (2-3) :83-127

[8]

BODLAENDER H, RUUCS8622 U UTR REP

[9]

BODLAENDER HL, 1990, LECT NOTES COMPUT SC, V411, P232

[10]

BODLAENDER HL, 1988, LECT NOTES COMPUT SC, V318, P223

← 1 2 3 4 →