@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},
volume = {26},
year = {1992},
pages = {257-286},
mrnumber = {1170326},
zbl = {0754.03006},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 257-286. http://gdmltest.u-ga.fr/item/ITA_1992__26_3_257_0/
1. , and , 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. , , and , 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. , et , Easy problems for tree decomposable graphs, J. Algorithms, 1991, 12, pp. 308-340. | MR 1105479 | Zbl 0734.68073
4. and , 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. and , Forbidden minors characterization of partial 3-trees, Discrete Math., 1990, 80, pp. 1-19. | MR 1045920 | Zbl 0701.05016
6. , Infinite hypergraphs, I, Basic proporties, Theoret. Comput. Sci., 1991, 82, pp. 177-214. | MR 1112768 | Zbl 0758.05069
7. and , Graph expressions and graph rewritings, Math. System Theory, 1987, 29, pp. 83-127. | MR 920770 | Zbl 0641.68115
8. , Classes of graphs wïth bounded tree-width, Report RUU-CS-86-22, University of Utrecht, The Netherlands, 1986.
9. , 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. , 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. , 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. , 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. , 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. , 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. , 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. , 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. , 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. and , Monadic second-order evaluations on tree-decomposable graphs, Rapport 90-110, Bordeaux-I, University, 1990. Theor. Comput. Sci., (to appear). | Zbl 0789.68083
19. and , On Search, decision and the efficiency of polynomial-time algorithms, A.C.M. Symp. on Theory of Computing 1989, pp. 501-512.
20. and , 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. , Hyperedge replacement: grammars and languages, Doctoral dissertation, University of Bremen 1989.
22. and , May we introduce to you: hyperedge replacement, L.N.C.S., 1987, 291, pp. 15-26. | Zbl 0643.68106
23. , Efficient algorithms on context-free graph languages, ICALP'88, Tampere, Finland, L.N.C.S., 1987, 317, pp. 362-378. | Zbl 0649.68075
24. , and , On some variations on the bandwidth minization problem, S.I.A.M. J. Comput., 1984, 13, pp. 650-667. | Zbl 0545.68058
25. and , Some new results on the well-quasi-ordering of graphs, Ann. Discrete Math., 1984, 23, pp. 343-354. | Zbl 0556.05058
26. and , Graph Minors IV, Tree-width and well quasiordering, J. Combin. Theory, Ser. B. 48, 1990, pp. 227-254. | MR 1046757 | Zbl 0719.05032
27. and , Graph Minors V, excluding a planar graph, J. Combin. Theory, Ser. B., 1986, 41, pp. 92-114. | MR 854606 | Zbl 0598.05055
28. and , Graph Minors X, Obstructions to tree-decomposition, Revised version, Feb. 1988.
29. and , Graph Minors XIII, The disjoint paths problem, Preprint, September 1986. | MR 1309358
30. and , Graph Minors XV, Wagner's conjecture, Revised version, March 1988.
31. , Ein Unentscheidbarkeitskreiterium, Wiss. Z. der Humbold Univ. Zu Berlin Math. Natur. Wiss., R24, 1975, pp. 772-780. | Zbl 0331.02026
32. , 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. , Graph algorithms, Handbook of Theoretical Computer Science, volume A", J. VAN LEEUWEN Ed., 1990, Elsevier, pp. 523-631. | MR 1127176 | Zbl 0900.68258
34. , 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. , Ueber eine Eigenshaft der ebenen Komplexe, Math. Ann., 1937, 114, pp. 570-590. | MR 1513158 | Zbl 0017.19005
36. and , Steiner trees, partial 2-trees, and IFI networks, Networks, 1983,13, pp. 159-167. | MR 706489 | Zbl 0529.68036
37. and , Finding minimal forbiden minors using a finite congruence, L.N.C.S. 510, 1991, pp. 532-543. | MR 1129933 | Zbl 0764.68122