A New Perspective on FO Model Checking of Dense Graph Classes

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	GAJARSKÝ Jakub HLINĚNÝ Petr LOKSHTANOV Daniel OBDRŽÁLEK Jan RAMANUJAN M S
Rok publikování	2020
Druh	Článek v odborném periodiku
Časopis / Zdroj	ACM Transactions on Computational Logic
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://dx.doi.org/10.1145/3383206
Doi	https://doi.org/10.1145/3383206
Klíčová slova	FO Logic; Model-Checking; Logic Interpretations; Sparse Graph Classes; Parameterized Complexity
Popis	Podáváme strukturální charakteristiku a algoritmicky efektivní zpracování tříd grafů, které mají FO interpretaci v grafech omezených stupňů.
Související projekty:	Structural properties, parameterized tractability and hardness in combinatorial problems