LAUSR

Core maintenance for dynamic hypergraphs has been receiving an increasing attention. However, existing works mainly focus on the insertion/deletion of hyperedges. This article revisits the problem from the view of vertices change. We study core maintenance when the vertices are inserted/deleted into/from specific hyperedges in the hypergraph, which is a challenging task since the deletion of the vertex may increase the core numbers and the insertion of the vertex may decrease the core numbers. We discuss in detail the possible changes of core numbers in different situations. For the insertion/deletion of vertices contained by a single hyperedge, we design sequential algorithms to discover the vertices whose core numbers have changed. Compared with static recomputation (Leng et al. 2013) and LYCLC (Luo et al. 2021) algorithms, our sequential algorithms can accelerate more than 1,000× and 12× at most in the processing time, respectively. For the insertion/deletion of vertices contained by different hyperedges, we find that core numbers of all vertices change 1 at most if these hyperedges form a matching. We design parallel algorithms that divide a matching into different sets based on their core numbers and allot a thread to each set. Experiments show that our parallel algorithms have good stability, scalability, and parallelism. Compared with the parallel static algorithm (Gabert et al. 2021) and the parallel dynamic algorithm GPC (Gabert et al. 2021), our parallel algorithms with 32 threads can accelerate 33× and 22× at most in the processing time, respectively.