上海科技大学知识管理系统

Motivated by power system cyber-physical security applications, this paper investigates a variant of connected dominating set (CDS) problem called relaxed connected dominating set (RCDS) problem, whereby between every two nodes in the solution dominating set there exists a path not traversing two consecutive nodes not in the set. The RCDS problem is NP-hard. To facilitate solving, presolving and problem reduction techniques are developed. In addition, three integer program formulations are obtained using single commodity flow, Dantzig-Fulkerson-Johnson and Miller-Tucker-Zemlin ideas to enforce graph connectedness. For a realistic power network repository (MATPOWER 7) including graphs with 70k nodes, our presolving and reduction procedures simplify problem instances to on average 30% of the original sizes. All reduced instances, when modeled by our formulations, can be solved with optimality gap less than 0.5% within 20 minutes using a PC with Gurobi 9. IEEE