A New Perspective on FO Model Checking of Dense Graph Classes

DOI10.1145/2933575.2935314zbMath1401.68196arXiv1805.01823OpenAlexW2531248283MaRDI QIDQ4635873

Petr Hliněný, Jan Obdržálek, Jakub Gajarský, Daniel Lokshtanov, M. S. Ramanujan

Publication date: 23 April 2018

Published in: ACM Transactions on Computational Logic, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicmodel checkinginterpretationsfixed-parameter tractabilityparameterized complexityalgorithmic metatheoremsbounded-degree graphssparse graph classesFO logiclogic interpretations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75)

Related Items (6)

FO model checking on geometric graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Unnamed Item ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: A New Perspective on FO Model Checking of Dense Graph Classes