A New Perspective on FO Model Checking of Dense Graph Classes

• 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
• www: http://dx.doi.org/10.1145/3383206
• Doi: http://dx.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