A matheuristic approach for solving the 2-connected dominating set problem

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Schlagworte:
  • Dominating Set Problem
  • GRASP
  • Matheuristic
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/aed26b4d-d5aa-4808-921f-69ad893baeeb