Monadic Second Order Logic on Graphs with Local Cardinality Constraints
From MaRDI portal
Publication:3599161
DOI10.1007/978-3-540-85238-4_49zbMath1173.03300OpenAlexW1517379197MaRDI QIDQ3599161
Publication date: 3 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_49
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25)
Related Items (4)
Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- General factors of graphs
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- On simple characterizations of k-trees
- Tractable cases of the extended global cardinality constraint
- Parametrized complexity theory.
- Easy problems for tree-decomposable graphs
- Equitable Coloring
- Mathematical Foundations of Computer Science 2004
- On Equitable Coloring of d-Degenerate Graphs
- Generalized finite automata theory with an application to a decision problem of second-order logic
- The factorization of graphs. II
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Monadic Second Order Logic on Graphs with Local Cardinality Constraints
