Reachability Is in DynFO
Reachability Is in DynFO
复制标题
DOI：
10.1145/3212685
复制
发表时间：
2018-09-01
影响因子：
2.5
通讯作者：
Zeume, Thomas
中科院分区：
文献类型：
--
作者：
Datta, Samir;Kulkarni, Raghav;Zeume, Thomas
Patnaik和Immerman引入了数据库查询的动态复杂性类DYNFO，可以通过辅助关系在插入和删除边缘的辅助关系的帮助下通过一阶动态程序维护。本文证实了他们的猜想，即可达性查询是在dynfo中。作为副产品，这表明可以在dyn fo中保持具有较小值的矩阵的等级。进一步表明，图的最大匹配（大小）可以保持在非均匀的dynfo（dynfo的扩展）中，并具有辅助关系的不均匀初始化。
Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges. This article confirms their conjecture that the reachability query is in DynFO.As a byproduct, it is shown that the rank of a matrix with small values can be maintained in Dyn FO. It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, an extension of DynFO, with non-uniform initialisation of the auxiliary relations.