Monadic second-order evaluations on tree-decomposable graphs
Tài liệu tham khảo
Arnborg, 1987, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277, 10.1137/0608024
Arnborg, 1990, An algebraic theory of graph reduction
Arnborg, 1991, Easy problems for tree decomposable graphs, J. Algorithms, 12, 308, 10.1016/0196-6774(91)90006-K
Arnborg, 1986, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305, 10.1137/0607033
Bauderon, 1987, Graph rewriting and graph expressions, Math. Systems Theory, 20, 83, 10.1007/BF01692060
Bern, 1987, Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216, 10.1016/0196-6774(87)90039-3
Bodlaender, 1988, Dynamic programming algorithms on graphs with bounded tree-width, Vol. 317, 223
Bodlaender, 1988, Improved self-reduction algorithms for graphs with bounded tree-width
Bodlaender, 1989, Complexity of path forming games
Bodlaender, 1990, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 631, 10.1016/0196-6774(90)90013-5
Bodlaender, 1991, Better algorithms for path-width and tree-width of graphs, Vol. 510
R.B. Borie, R.G. Parker and C.A. Tovey, Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, to appear.
Courcelle, 1990, Graph rewriting: an algebraic and logic approach, Vol. B, 193
Courcelle, 1990, The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 12, 10.1016/0890-5401(90)90043-H
Courcelle, 1991, The monadic second-order logic of graphs V: on closing the gap between definability and recognizability, Theoret. Comput. Sci., 80, 53, 10.1016/0304-3975(91)90387-H
Courcelle, 1992, Monadic second-order definable transductions, Lecture Notes in Computer Science, 10.1007/3-540-55251-0_7
Deransart, 1988, Attribute grammars, Vol. 323
Garey, 1979
Habel, 1989, Hyperedge replacement: grammars and languages
Habel, 1989, Decidable boundness problems for hyperedge replacement graph grammars, Vol. 351, 275
Hohberg, 1990, A framework to algorithms for optimization problems on graphs
Johnson, 1985, The NP-completeness column: an ongoing guide (16th), J. Algorithms, 6, 434, 10.1016/0196-6774(85)90012-4
Lagergren, 1990, Efficient parallel algorithms for tree-decomposition and related problems, Proc. IEEE Symp. on FOCS, 173
Miyano, 1989, The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Math. Systems Theory, 22, 47, 10.1007/BF02088292
Takamizawa, 1982, Linear-time computability of combinatorial problems on series–parallel graphs, J. Assoc. Comput. Mach., 29, 623, 10.1145/322326.322328
Thatcher, 1968, Generalized finite automata theory with an application to a decision problem in second-order logic, Math. Systems Theory, 2, 57, 10.1007/BF01691346
Valdes, 1982, The recognition of series-parallel digraphs, SIAM J. Comput., 11, 289, 10.1137/0211023
Wimer, 1987, Linear algorithms on k-terminal graphs