Monadic second order logic on graphs with local cardinality constraints

DOI10.1145/1877714.1877718zbMATH Open1351.68121OpenAlexW2026493143WikidataQ130877241 ScholiaQ130877241MaRDI QIDQ2946629FDOQ2946629

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

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 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)

Cited In (11)

• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extended MSO model checking via small vertex integrity
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• An approval-based model for single-step liquid democracy
• Weighted proper orientations of trees and graphs of bounded treewidth
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough

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)