Monadic second order logic on graphs with local cardinality constraints

DOI10.1145/1877714.1877718zbMath1351.68121OpenAlexW2026493143WikidataQ130877241 ScholiaQ130877241MaRDI QIDQ2946629

Stefan Szeider

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1877714.1877718

zbMATH Keywords

treewidthNP-hardnessW[1-hardness]cardinality constraintMSO model checking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Weighted proper orientations of trees and graphs of bounded treewidth ⋮ An approval-based model for single-step liquid democracy ⋮ Extended MSO model checking via small vertex integrity ⋮ Tractable answer-set programming with weight constraints: bounded treewidth is not enough ⋮ Unnamed Item ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization

This page was built for publication: Monadic second order logic on graphs with local cardinality constraints