FO Model Checking of Interval Graphs
FO Model Checking of Interval Graphs
复制标题
区间图的 FO 模型检验
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jakub Teska
中科院分区：
文献类型：
--
作者：
R. Ganian;Petr Hliněný;D. Král;J. Obdržálek;Jarett Schwartz;Jakub Teska
我们研究区间图（即实线上区间的交集图）上 FO 模型检查问题的计算复杂性。主要的积极结果是，对于 n 顶点区间图，这个问题可以在时间 O(n logn) 内得到解决，该图的表示仅包含来自指定有限集的长度的区间。我们通过证明如果长度限制于某个开放子集中的任何密集集合（例如，在集合 (1, 1+e) 中），则情况不成立，从而补充此结果。
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that this problem can be solved in time O(n logn) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in some open subset, e.g., in the set (1, 1+e).