Incremental update algorithm for minimal dominating set of dynamic undirected graphs
Hongtao Zhang · Journal of Physics Conference Series · 2024
Abstract Minimum dominating set is a basic graph problem. Most existing solving algorithms are designed for static graphs. In this paper, an incremental update algorithm is proposed to solve the minimal dominating set of a dynamic graph. This algorithm can quickly update the MDS when the structure of graph changes, and not need to recalculate based on the entire graph. By analyzing the characteristics of the four structural changes (adding vertices, deleting vertices, adding edges, and deleting edges) in the graph, a local update strategy for the minimal dominating set is designed, and a reduction rule for the minimal dominating set is proposed. This not only effectively reduces the computational complexity, but also enables the algorithm results to approach the minimum dominating set. Compared with traditional static algorithms, our algorithm has higher efficiency and accuracy in calculating the minimal dominating set of dynamic graphs.