In the hypergraph H,the(k,t)-hypercore HC(k,t)is the maximal subhypergraph with δ(HC(k,t))≥ k and each hyperedge satisfying the fraction constraint about t.The fraction constraint about t is that the ratio of the number of vertices a hyperedge contains in the subhypergraph to the number of vertices it contains in H is not less than t.For each vertex u ∈ H,the t-hypercore number of u is the maximal k among all(k,t)-hypercores containing u.In this paper,we study the hypercore maintenance problem that is updating the t-hypercore numbers of vertices on dynamic hypergraphs.Firstly,we prove the necessary conditions satisfied by vertices whose t-hypercore numbers change when a hyperedge is inserted or deleted,and accordingly design(k,t)-hypercore maintenance algorithms for these cases,and give the parallel algorithm.Then,we study the(k,t)-hypercore maintenance problem for batch insertion or deletion of hyperedges.We define the dominant vertices disjoint hyperedge set(DDHS)and prove that each vertex's t-hypercore number can change by at most 1 after inserting or deleting a DDHS on a hypergraph.Finally,a parallel batch(k,t)-hyperedge maintenance algorithm is designed by DDHS.This algorithm is more efficient than the maintenance algorithms with single hyperedge change.
关键词
超图/(k,t)-超核/超核维护/并行算法/批量处理
Key words
hypergraph/(k,t)-hypercore/hypercore maintenance/parallel algorithm/batch process
万方数据