scientific article

zbMath0662.03030MaRDI QIDQ3812222

Stefan Arnborg, Jens Lagergren, Detlef Seese

Publication date: 1988

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph propertieslinear timefinite graphsgraphs of fixed bounded tree-widthMonadic second order logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Graph theory (05C99) Second- and higher-order model theory (03C85)

Related Items (25)

Trees, grids, and MSO decidability: from graphs to matroids ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ Generalized coloring for tree-like graphs ⋮ Tree clustering for constraint networks ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Decomposition width of matroids ⋮ NC-algorithms for graphs with small treewidth ⋮ Undecidability of the bandwidth problem on linear graph languages ⋮ 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 parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Branch-width, parse trees, and monadic second-order logic for matroids. ⋮ Power indices and easier hard problems ⋮ Unnamed Item ⋮ Achromatic number is NP-complete for cographs and interval graphs ⋮ Generating irregular partitionable data structures ⋮ On hyperedge replacement and BNLC graph grammars ⋮ Steiner's problem in double trees ⋮ The structure of the models of decidable monadic theories of graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ The Steiner tree polytope and related polyhedra

This page was built for publication: