Photo by benjaminzanatta from unsplash
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… Click to show full abstract
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.
Keywords:
approach solving;
matheuristic approach;
dominating set;
connected dominating;
solving connected;
set problem
Journal Title: Applicable Analysis and Discrete Mathematics
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Applicable Analysis and Discrete Mathematics
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!