Monadic second-order evaluations on tree-decomposable graphs
From MaRDI portal
Publication:685464
DOI10.1016/0304-3975(93)90064-ZzbMath0789.68083MaRDI QIDQ685464
Publication date: 20 June 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
monadic second-order logiclinear algorithmsderivation treefunctions on graphshyperedge replacement graph-grammarsemiring homomorphisms
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Related Items
Monadic second-order definable graph transductions: a survey ⋮ Finite tree automata with cost functions ⋮ Safe separators for treewidth ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ A new approach on locally checkable problems ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Probabilistic hyperedge replacement grammars ⋮ Planar disjoint-paths completion ⋮ A general framework for path convexities ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Courcelle's theorem for triangulations ⋮ A local characterization of bounded clique-width for line graphs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Parameterized complexity of fair deletion problems ⋮ Logical description of context-free graph languages ⋮ Kernel bounds for path and cycle problems ⋮ On the computational complexity of the bipartizing matching problem ⋮ Algebras for Tree Decomposable Graphs ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Treelength of series-parallel graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ Query efficient implementation of graphs of bounded clique-width ⋮ Unnamed Item ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Least solutions of equations over N ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ Upper bounds to the clique width of graphs ⋮ Algorithms for decision problems in argument systems under preferred semantics ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Waypoint routing on bounded treewidth graphs ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ Frameworks for designing in-place graph algorithms ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ A Practical Approach to Courcelle's Theorem ⋮ Partitioning graphs of supply and demand ⋮ Querying linguistic treebanks with monadic second-order logic in linear time ⋮ Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width ⋮ Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the OBDD size for graphs of bounded tree- and clique-width ⋮ A comparison of compatible, finite, and inductive graph properties ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ All structured programs have small tree width and good register allocation ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Nondeterministic operations on finite relational structures ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ The monadic second-order logic of graphs. XII: Planar graphs and planar maps ⋮ Partial and perfect path covers of cographs ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ On the Tree-Width of Planar Graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Tree decompositions and social graphs ⋮ Structural tractability of enumerating CSP solutions ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ Listing all potential maximal cliques of a graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hyperedge replacement: grammars and languages
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Complexity of path-forming games
- Attribute grammars. Definitions, systems and bibliography
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Easy problems for tree-decomposable graphs
- Characterization and Recognition of Partial 3-Trees
- The NP-completeness column: an ongoing guide
- Complexity of Finding Embeddings in a k-Tree
- Graph expressions and graph rewritings
- The Recognition of Series Parallel Digraphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
- Generalized finite automata theory with an application to a decision problem of second-order logic
This page was built for publication: Monadic second-order evaluations on tree-decomposable graphs
