Deciding First-Order Properties of Nowhere Dense Graphs

DOI10.1145/3051095zbMath1426.68172arXiv1311.3899MaRDI QIDQ4640289

Stephan Kreutzer, Sebastian Siebertz, Martin Grohe

Publication date: 17 May 2018

Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

nowhere dense graphs; algorithmic graph structure theory; first-order model-checking

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q60: Specification and verification (program logics, model checking, etc.)

05C75: Structural characterization of families of graphs

03B25: Decidability of theories and sets of sentences

68Q19: Descriptive complexity and finite models

05C57: Games on graphs (graph-theoretic aspects)

05C42: Density (toughness, etc.)

Uses Software

• SuLQ