The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992) no. 3, pp. 257-286.
@article{ITA_1992__26_3_257_0,
author = {Courcelle, B.},
title = {The monadic second-order logic of graphs {III} : tree-decompositions, minors and complexity issues},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {257--286},
publisher = {EDP-Sciences},
volume = {26},
number = {3},
year = {1992},
zbl = {0754.03006},
mrnumber = {1170326},
language = {en},
url = {http://www.numdam.org/item/ITA_1992__26_3_257_0/}
}
TY  - JOUR
AU  - Courcelle, B.
TI  - The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1992
DA  - 1992///
SP  - 257
EP  - 286
VL  - 26
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1992__26_3_257_0/
UR  - https://zbmath.org/?q=an%3A0754.03006
UR  - https://www.ams.org/mathscinet-getitem?mr=1170326
LA  - en
ID  - ITA_1992__26_3_257_0
ER  - 
Courcelle, B. The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992) no. 3, pp. 257-286. http://www.numdam.org/item/ITA_1992__26_3_257_0/

1. S. Arnborg, D. Corneil and A. Proskurowski, Complexity of finding an embedding in a k-tree, S.I.A.M. J. Alg. Disc. Methods, 1987, 8, pp. 277-284. | MR 881187 | Zbl 0611.05022

2. S. Arnborg, B. Courcelle, A. Proskurowski and D. Seese, An algebraic theory of graph reduction, Report 90-02, Bordeaux-I University, 1990. Short version in L.N.C.S., 532, 1991, pp. 70-83. | MR 1431274 | Zbl 0765.68062

3. S. Arnborg, J. Lagergren et D. Seese, Easy problems for tree decomposable graphs, J. Algorithms, 1991, 12, pp. 308-340. | MR 1105479 | Zbl 0734.68073

4. S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, S.I.A.M. J. Alg. Disc. Meth., 1986, 7, pp. 305-314. | MR 830649 | Zbl 0597.05027

5. S. Arnborg A. Proskurowski and D. Corneil, Forbidden minors characterization of partial 3-trees, Discrete Math., 1990, 80, pp. 1-19. | MR 1045920 | Zbl 0701.05016

6. M. Bauderon, Infinite hypergraphs, I, Basic proporties, Theoret. Comput. Sci., 1991, 82, pp. 177-214. | MR 1112768 | Zbl 0758.05069

7. M. Bauderon and B. Courcelle, Graph expressions and graph rewritings, Math. System Theory, 1987, 29, pp. 83-127. | MR 920770 | Zbl 0641.68115

8. H. Bodlaender, Classes of graphs wïth bounded tree-width, Report RUU-CS-86-22, University of Utrecht, The Netherlands, 1986.

9. H. Bodlaender, Polynomial algorithms for Chromatic Index and Graph Isomorphism on partial k-trees, Proc. First Scandinavian Workshop on Algorithm theory, 1988, Lecture Notes in Comput. Sci., 318, pp. 223-232. | MR 1019374 | Zbl 0651.68079

10. H. Bodlaender, Dynamic programming on graphs with bounded tree width, Proceedings of ICALP'88, Tampere, Finland, L.N.C.S, 317, 1988, pp. 105-118. | MR 1023630 | Zbl 0649.68039

11. H. Bodlaender, Improved self-reduction algorithms for graphs with bounded tree-width, Proceedings of WG'89, Lecture Notes in Comput. Sci., 1990, 411, pp. 232-244. | MR 1063946 | Zbl 0768.68033

12. B. Courcelle, An axiomatic definition of eontext-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 1987, 55, pp. 141-181. | MR 932445 | Zbl 0644.68095

13. B. Courcelle, The monadic second-order theory of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 1990, 85, pp. 12-75. | MR 1042649 | Zbl 0722.03008

14. B. Courcelle, The monadic second-order logie of graphs II: Infinite graphs of bounded with, Math. Systems Theory, 1989, 21, pp. 187-221. | MR 987150 | Zbl 0694.68043

15. B. Courcelle, The monadic second-order logic of graphs IV, Definability results for equational graphs, Ann. Pure Appl. Logic, 1990, 49, pp. 193-255. | MR 1077259 | Zbl 0731.03006

16. B. Courcelle, The monadic second-order logic of graphs VI: On several representations of graphs by logical structures, Research report 89-99, Bordeaux I-University. Discrete Appl. Math. (in press). (See also Logic in Comput. Sci., 1990. Philadelphia). | Zbl 0809.03005

17. B. Courcelle, Graph rewriting: an algebraic and logic approach, in Handbook of Theoretical computer Science, vol. B, J. VAN LEEUWEN Ed. 1990, Elsevier, pp. 193-242. | Zbl 0900.68282

18. B. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Rapport 90-110, Bordeaux-I, University, 1990. Theor. Comput. Sci., (to appear). | Zbl 0789.68083

19. M. Fellows and M. Langston, On Search, decision and the efficiency of polynomial-time algorithms, A.C.M. Symp. on Theory of Computing 1989, pp. 501-512.

20. M. Fellows and M. Langston, An analogue of the Myhill-Nerode Theorem and its use in computing finite-basis characterization, 30th Annual I.E.E.E. Symp. on Foundations of Computer Science, 1989, pp. 520-525.

21. A. Habel, Hyperedge replacement: grammars and languages, Doctoral dissertation, University of Bremen 1989.

22. A. Habel and H. J. Kreowski, May we introduce to you: hyperedge replacement, L.N.C.S., 1987, 291, pp. 15-26. | Zbl 0643.68106

23. C. Lautemann, Efficient algorithms on context-free graph languages, ICALP'88, Tampere, Finland, L.N.C.S., 1987, 317, pp. 362-378. | Zbl 0649.68075

24. J. Leung, J. Witthof and O. Vornberger, On some variations on the bandwidth minization problem, S.I.A.M. J. Comput., 1984, 13, pp. 650-667. | Zbl 0545.68058

25. N. Robertson and P. Seymour, Some new results on the well-quasi-ordering of graphs, Ann. Discrete Math., 1984, 23, pp. 343-354. | Zbl 0556.05058

26. N. Robertson and P. Seymour, Graph Minors IV, Tree-width and well quasiordering, J. Combin. Theory, Ser. B. 48, 1990, pp. 227-254. | MR 1046757 | Zbl 0719.05032

27. N. Robertson and P. Seymour, Graph Minors V, excluding a planar graph, J. Combin. Theory, Ser. B., 1986, 41, pp. 92-114. | MR 854606 | Zbl 0598.05055

28. N. Robertson and P. Seymour, Graph Minors X, Obstructions to tree-decomposition, Revised version, Feb. 1988.

29. N. Robertson and P. Seymour, Graph Minors XIII, The disjoint paths problem, Preprint, September 1986. | MR 1309358

30. N. Robertson and P. Seymour, Graph Minors XV, Wagner's conjecture, Revised version, March 1988.

31. D. Seese, Ein Unentscheidbarkeitskreiterium, Wiss. Z. der Humbold Univ. Zu Berlin Math. Natur. Wiss., R24, 1975, pp. 772-780. | Zbl 0331.02026

32. D. Seese, The structure of the models of decidable monadic theories of graphs. Ann. Pure and Appl. Logic, 1991, 53, pp. 169-195. | MR 1114848 | Zbl 0733.03026

33. J. Van Leeuwen, Graph algorithms, Handbook of Theoretical Computer Science, volume A", J. VAN LEEUWEN Ed., 1990, Elsevier, pp. 523-631. | MR 1127176 | Zbl 0900.68258

34. W. Vogler, Recognizing edge replacement graphs languages in cubic time, Proceedings of the 4th Int. Workshop on Graph Grammars, Bremen 1990, L.N.C.S., 532, 1991, pp. 676-687. | MR 1431296 | Zbl 0769.68078

35. K. Wagner, Ueber eine Eigenshaft der ebenen Komplexe, Math. Ann., 1937, 114, pp. 570-590. | MR 1513158 | Zbl 0017.19005

36. J. Wald and C. Colbourn, Steiner trees, partial 2-trees, and IFI networks, Networks, 1983,13, pp. 159-167. | MR 706489 | Zbl 0529.68036

37. J. Lagergren and S. Arnborg, Finding minimal forbiden minors using a finite congruence, L.N.C.S. 510, 1991, pp. 532-543. | MR 1129933 | Zbl 0764.68122