Incremental maintenance of maximal cliques in a dynamic graph
Incremental maintenance of maximal cliques in a dynamic graph
复制标题
DOI：
10.1007/s00778-019-00540-5
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
A. Das;Michael Svendsen;Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
A. Das;Michael Svendsen;Srikanta Tirthapura
我们考虑通过边的添加或删除而变化的动态图中所有极大团的集合的维护问题。我们给出了图中添加边时最大团集合变化幅度的近乎严格的界，以及第一个边添加下增量团维护的变化敏感算法，当添加的边数较小时，其运行时间与最大团集合中变化的大小成正比。当图中的边被删除时，我们的算法也可以应用于递减的情况。我们给出的实验结果表明，这些算法在实践中是有效的，并且比以前的工作快两到三个数量级。
We consider the maintenance of the set of all maximal cliques in a dynamic graph that is changing through the addition or deletion of edges. We present nearly tight bounds on the magnitude of change in the set of maximal cliques when edges are added to the graph, as well as the first change-sensitive algorithm for incremental clique maintenance under edge additions, whose runtime is proportional to the magnitude of the change in the set of maximal cliques, when the number of edges added is small. Our algorithm can also be applied to the decremental case, when edges are deleted from the graph. We present experimental results showing these algorithms are efficient in practice and are faster than prior work by two to three orders of magnitude.