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í: 2016
• Druh: Článek ve sborníku
• Konference: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://lics.rwth-aachen.de/lics16/
• Doi: http://dx.doi.org/10.1145/2933575.2935314
• Obor: Informatika
• 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

• Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
• Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.
• Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity