超图上(k,t)-超核维护问题的快速算法献给刘桂真教授80寿辰  

Fast algorithms for the(k,t)-hypercore maintenance problem on hypergraphs

作　　者：张飞腾 刘彬[1] 方奇志[1] Feiteng Zhang;Bin Liu;Qizhi Fang

机构地区：[1]中国海洋大学数学科学学院,青岛266000

出　　处：《中国科学：数学》2024年第11期1865-1888,共24页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11971447)资助项目。

摘　　要：超图H上的(k,t)-超核是最小度不小于k且每条超边满足关于t的比例约束的极大子超图,其中比例约束是指超边在子超图中包含的顶点数与它在H中包含顶点数之比不小于t.在参数t为常数的前提下,每个顶点的t-超核数为其所在所有(k,t)-超核中的最大的k.本文研究在动态超图上更新每个顶点的t-超核数这一超核维护问题.首先,本文刻画单超边插入或删除时t-超核数发生变化的顶点所满足的必要条件,据此设计出该情形下的维护算法,并给出其并行算法.然后,本文研究批量插入或删除超边的情形.定义主导顶点不交超边集DDHS(dominant vertices disjoint hyperedge set)并证明在超图上一次插入或删除一个DDHS后每个顶点t-超核数至多变化1.最后,本文通过DDHS设计出并行批量(k,t)-超核维护算法.相比于单超边改变的维护算法,该算法效率更高.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 2 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)-超核 超核维护 并行算法 批量处理 

分 类 号：O157.5[理学—数学]