The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.

DOI10.1016/S0304-3975(02)00578-9zbMath1038.68048OpenAlexW2008770438MaRDI QIDQ1874383

No author found.

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00578-9

zbMATH Keywords

monadic second-order logicgraphshypergraphssparseclique-widthtree-widthedge set quantifications

Mathematics Subject Classification ID

Related Items (17)

Trees, grids, and MSO decidability: from graphs to matroids ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Meta-kernelization using well-structured modulators ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ A monadic second-order definition of the structure of convex hypergraphs. ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Clique-width of countable graphs: A compactness property. ⋮ The Descriptive Complexity of Parity Games ⋮ Circle graphs and monadic second-order logic ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ GETGRATS ⋮ Graph Operations, Graph Transformations and Monadic Second-Order Logic: ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ The recognizability of sets of graphs is a robust property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• The structure of the models of decidable monadic theories of graphs
• A partial k-arboretum of graphs with bounded treewidth
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Logical description of context-free graph languages
• The monadic second-order logic of graphs. VIII: Orientations
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Languages that Capture Complexity Classes
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.