The dynamic descriptive complexity of k-clique
The dynamic descriptive complexity of k-clique
复制标题
k-clique的动态描述复杂度
DOI：
10.1016/j.ic.2017.04.005
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thomas Zeume
中科院分区：
文献类型：
--
作者：
Thomas Zeume
在这项工作中，研究了 k-clique 查询的动态描述复杂性。结果表明，当只能插入边时，k-clique 可以通过数量为 k−1 的无量词更新程序来维护，但不能通过数量为 k−2 的无量词更新程序来维护（即使存在一元辅助函数）。这为插入下的无量词更新程序的图形查询建立了一个数量层次结构。下界的证明使用拉姆齐数的上限和下界。
In this work the dynamic descriptive complexity of the k-clique query is studied. It is shown that when edges may only be inserted then k-clique can be maintained by a quantifier-free update program of arity k− 1, but it cannot be maintained by a quantifier-free update program of arity k− 2 (even in the presence of unary auxiliary functions). This establishes an arity hierarchy for graph queries for quantifier-free update programs under insertions. The proof of the lower bound uses upper and lower bounds for Ramsey numbers.
登录
查看更多内容
影响因子：
0.5
作者：
Gelade, Wouter;Marquardt, Marcel;Schwentick, Thomas
通讯作者：
Schwentick, Thomas
确定性 FOIES 较弱
影响因子：
1.2
作者：
Guozhu Dong;Jianwen Su
通讯作者：
Jianwen Su
关系演算和SQL中递归查询不可能递减重新计算的问题
DOI：
--
发表时间：
1995
期刊：
International Workshop/Symposium on Database Programming Languages
影响因子：
--
作者：
Guozhu Dong;L. Libkin;L. Wong
通讯作者：
L. Wong
关于可达性的无量词动态复杂性
影响因子：
1
作者：
T. Zeume;T. Schwentick
通讯作者：
T. Schwentick
传递闭包的动态复杂度在 DynTC0 中
影响因子：
1.1
作者：
W. Hesse
通讯作者：
W. Hesse