Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes

DOI10.1007/978-3-642-45278-9_15zbMath1284.68463arXiv1306.5571OpenAlexW1530056612MaRDI QIDQ2870025

Robert Ganian, Jan Obdržálek

Publication date: 17 January 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.5571

zbMATH Keywords

integer linear programmingmodel checkingtime complexityvertex coverlinear cardinality constraintsmonadic second-order logic on finite graphsmonadic second-order model checkingMSO partitioning problem

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) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Extended MSO model checking via small vertex integrity ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Unnamed Item ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems

This page was built for publication: Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes