submitted on 2024-09-15, 12:30 and posted on 2024-09-15, 12:32authored byRaka Jovanovic, Stefan Voß
This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to find near optimal solutions for large graphs. The algorithm is based on a Greedy Randomized Adaptive Search Procedure (GRASP). Its performance is enhanced by combining it with a second local search method that uses a Mixed Integer Program. The performance of the proposed method is evaluated on large unit disc graphs having varying edge densities and on general graphs.