Publication:3812222
From MaRDI portal
zbMath0662.03030MaRDI QIDQ3812222
Jens Lagergren, Stefan Arnborg, Detlef Seese
Publication date: 1988
graph properties; linear time; finite graphs; graphs of fixed bounded tree-width; Monadic second order logic
68Q25: Analysis of algorithms and problem complexity
03B25: Decidability of theories and sets of sentences
05C99: Graph theory
03C85: Second- and higher-order model theory
Related Items
Power indices and easier hard problems, The structure of the models of decidable monadic theories of graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Trees, grids, and MSO decidability: from graphs to matroids, Undecidability of the bandwidth problem on linear graph languages, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Tree clustering for constraint networks, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, A regular characterization of graph languages definable in monadic second-order logic, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, General vertex disjoint paths in series-parallel graphs, On hyperedge replacement and BNLC graph grammars, The Steiner tree polytope and related polyhedra, The nonexistence of reduction rules giving an embedding into a \(k\)-tree, Regularity and locality in \(k\)-terminal graphs, Generalized coloring for tree-like graphs, Generating irregular partitionable data structures, Achromatic number is NP-complete for cographs and interval graphs, Steiner's problem in double trees, Branch-width, parse trees, and monadic second-order logic for matroids., The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
