Monadic second order logic on graphs with local cardinality constraints

DOI10.1145/1877714.1877718MaRDI QIDQ2946629zbMATHOpenAlexWikidataFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)

Recommendations

• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• Expanding the expressive power of monadic second-order logic on restricted graph classes
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• scientific article; zbMATH DE number 4081531

Cited in

(12)

• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• An approval-based model for single-step liquid democracy
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Extended MSO model checking via small vertex integrity
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Parameterized complexity of fair vertex evaluation problems
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• Expanding the expressive power of monadic second-order logic on restricted graph classes
• scientific article; zbMATH DE number 1290983 (Why is no real title available?)
• Weighted proper orientations of trees and graphs of bounded treewidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946629)