Manara - Qatar Research Repository
Browse

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

Download (387.56 kB)
journal contribution
submitted on 2024-09-15, 12:30 and posted on 2024-09-15, 12:32 authored by Raka 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.

Other Information

Published in: Applicable Analysis and Discrete Mathematics
License: http://creativecommons.org/licenses/by/4.0/
See article on publisher's website: https://dx.doi.org/10.2298/aadm190227052j

History

Language

  • English

Publisher

National Library of Serbia

Publication Year

  • 2019

License statement

This Item is licensed under the Creative Commons Attribution 4.0 International License.

Institution affiliated with

  • Hamad Bin Khalifa University
  • Qatar Environment and Energy Research Institute - HBKU

Usage metrics

    Qatar Environment and Energy Research Institute - HBKU

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC