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},
     mrnumber = {1170326},
     zbl = {0754.03006},
     language = {en},
     url = {http://archive.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
SP  - 257
EP  - 286
VL  - 26
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1992__26_3_257_0/
LA  - en
ID  - ITA_1992__26_3_257_0
ER  - 
%0 Journal Article
%A Courcelle, B.
%T The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1992
%P 257-286
%V 26
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1992__26_3_257_0/
%G en
%F ITA_1992__26_3_257_0
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://archive.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 | Zbl

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 | Zbl

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

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 | Zbl

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

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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

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

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

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

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 | Zbl

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

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

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

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 | Zbl

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

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 | Zbl

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

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

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