The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

 Access to full text

 Full (PDF)

1. 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. Zbl0611.05022MR881187
2. 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. Zbl0765.68062MR1431274
3. 3. S. ARNBORG, J. LAGERGREN et D. SEESE, Easy problems for tree decomposable graphs, J. Algorithms, 1991, 12, pp. 308-340. Zbl0734.68073MR1105479
4. 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. Zbl0597.05027MR830649
5. 5. S. ARNBORG A. PROSKUROWSKI and D. CORNEIL, Forbidden minors characterization of partial 3-trees, Discrete Math., 1990, 80, pp. 1-19. Zbl0701.05016MR1045920
6. 6. M. BAUDERON, Infinite hypergraphs, I, Basic proporties, Theoret. Comput. Sci., 1991, 82, pp. 177-214. Zbl0758.05069MR1112768
7. 7. M. BAUDERON and B. COURCELLE, Graph expressions and graph rewritings, Math. System Theory, 1987, 29, pp. 83-127. Zbl0641.68115MR920770
8. 8. H. BODLAENDER, Classes of graphs wïth bounded tree-width, Report RUU-CS-86-22, University of Utrecht, The Netherlands, 1986. 
9. 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. Zbl0651.68079MR1019374
10. 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. Zbl0649.68039MR1023630
11. 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. Zbl0768.68033MR1063946
12. 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. Zbl0644.68095MR932445
13. 13. B. COURCELLE, The monadic second-order theory of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 1990, 85, pp. 12-75. Zbl0722.03008MR1042649
14. 14. B. COURCELLE, The monadic second-order logie of graphs II: Infinite graphs of bounded with, Math. Systems Theory, 1989, 21, pp. 187-221. Zbl0694.68043MR987150
15. 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. Zbl0731.03006MR1077259
16. 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). Zbl0809.03005
17. 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. Zbl0900.68282
18. 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). Zbl0789.68083
19. 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. 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. 21. A. HABEL, Hyperedge replacement: grammars and languages, Doctoral dissertation, University of Bremen 1989. 
22. 22. A. HABEL and H. J. KREOWSKI, May we introduce to you: hyperedge replacement, L.N.C.S., 1987, 291, pp. 15-26. Zbl0643.68106
23. 23. C. LAUTEMANN, Efficient algorithms on context-free graph languages, ICALP'88, Tampere, Finland, L.N.C.S., 1987, 317, pp. 362-378. Zbl0649.68075
24. 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. Zbl0545.68058
25. 25. N. ROBERTSON and P. SEYMOUR, Some new results on the well-quasi-ordering of graphs, Ann. Discrete Math., 1984, 23, pp. 343-354. Zbl0556.05058
26. 26. N. ROBERTSON and P. SEYMOUR, Graph Minors IV, Tree-width and well quasiordering, J. Combin. Theory, Ser. B. 48, 1990, pp. 227-254. Zbl0719.05032MR1046757
27. 27. N. ROBERTSON and P. SEYMOUR, Graph Minors V, excluding a planar graph, J. Combin. Theory, Ser. B., 1986, 41, pp. 92-114. Zbl0598.05055MR854606
28. 28. N. ROBERTSON and P. SEYMOUR, Graph Minors X, Obstructions to tree-decomposition, Revised version, Feb. 1988. 
29. 29. N. ROBERTSON and P. SEYMOUR, Graph Minors XIII, The disjoint paths problem, Preprint, September 1986. Zbl0823.05038MR1309358
30. 30. N. ROBERTSON and P. SEYMOUR, Graph Minors XV, Wagner's conjecture, Revised version, March 1988. 
31. 31. D. SEESE, Ein Unentscheidbarkeitskreiterium, Wiss. Z. der Humbold Univ. Zu Berlin Math. Natur. Wiss., R24, 1975, pp. 772-780. Zbl0331.02026
32. 32. D. SEESE, The structure of the models of decidable monadic theories of graphs. Ann. Pure and Appl. Logic, 1991, 53, pp. 169-195. Zbl0733.03026MR1114848
33. 33. J. VAN LEEUWEN, Graph algorithms, Handbook of Theoretical Computer Science, volume A", J. VAN LEEUWEN Ed., 1990, Elsevier, pp. 523-631. Zbl0900.68258MR1127176
34. 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. Zbl0769.68078MR1431296
35. 35. K. WAGNER, Ueber eine Eigenshaft der ebenen Komplexe, Math. Ann., 1937, 114, pp. 570-590. Zbl0017.19005MR1513158
36. 36. J. WALD and C. COLBOURN, Steiner trees, partial 2-trees, and IFI networks, Networks, 1983,13, pp. 159-167. Zbl0529.68036MR706489
37. 37. J. LAGERGREN and S. ARNBORG, Finding minimal forbiden minors using a finite congruence, L.N.C.S. 510, 1991, pp. 532-543. Zbl0764.68122MR1129933

1. Masayoshi Matsushita, Yota Otachi, Toru Araki, Completely Independent Spanning Trees in (Partial) k-Trees
2. Salvatore La Torre, Margherita Napoli, Automata-based representations for infinite graphs
3. Salvatore La Torre, Margherita Napoli, Automata-based Representations for Infinite Graphs