A New Perspective on FO Model Checking of Dense Graph Classes
A New Perspective on FO Model Checking of Dense Graph Classes
复制标题
密集图类 FO 模型检查的新视角
DOI：
10.1145/3383206
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Ramanujan
中科院分区：
文献类型：
--
作者：
Jakub Gajarský;Petr Hliněný;J. Obdržálek;D. Lokshtanov;M. Ramanujan
我们研究了稠密图类的一阶（FO）模型检测问题，即那些在稀疏图类中具有FO解释（或FO转换）的模型检测问题。我们给出了有界度图中FO可解释的图类的结构特征。这种特征使我们能够有效地计算输入图的FO解释。因此，我们得到一个FPT算法的后继不变FO模型检查任何图形类，是FO解释（或FO转导）的图形类的有界度。我们用来获得这些结果的方法也可能是独立的利益。
We study the first-order (FO) model checking problem of dense graph classes, namely, those that have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes that are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking on any graph class that is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.
排除拓扑子图的图上的后继不变一阶逻辑
DOI：
10.4230/lipics.csl.2016.18
发表时间：
2016
期刊：
影响因子：
--
作者：
K. Eickmeyer;K. Kawarabayashi
通讯作者：
K. Kawarabayashi
DOI：
10.2168/lmcs-6(2:2)2010
发表时间：
2010
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
A. Blumensath;B. Courcelle
通讯作者：
B. Courcelle