A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem

Raka Jovanovic; Stefan Voβ

doi:10.2298/AADM190227052J

A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem

Raka Jovanovic^*, Stefan Voβ^*

^*Corresponding author for this work

QEERI - Energy Center

University of Hamburg

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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 and 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.

Original language	English
Pages (from-to)	775-799
Number of pages	25
Journal	Applicable Analysis and Discrete Mathematics
Volume	14
Issue number	3
DOIs	https://doi.org/10.2298/AADM190227052J
Publication status	Published - 2020

Keywords

Dominating Set Problem
GRASP
Matheuristic

Access to Document

10.2298/AADM190227052J

Cite this

@article{8a5d8505a01e4d48bcd3203c74079c18,

title = "A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem",

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 and 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 = "Dominating Set Problem, GRASP, Matheuristic",

author = "Raka Jovanovic and Stefan Voβ",

year = "2020",

doi = "10.2298/AADM190227052J",

language = "English",

volume = "14",

pages = "775--799",

journal = "Applicable Analysis and Discrete Mathematics",

issn = "1452-8630",

publisher = "University of Belgrade",

number = "3",

}

TY - JOUR

T1 - A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem

AU - Jovanovic, Raka

AU - Voβ, Stefan

PY - 2020

Y1 - 2020

N2 - This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to and 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.

AB - This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to and 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.

KW - Dominating Set Problem

KW - GRASP

KW - Matheuristic

UR - https://www.scopus.com/pages/publications/85100387227

U2 - 10.2298/AADM190227052J

DO - 10.2298/AADM190227052J

M3 - Article

AN - SCOPUS:85100387227

SN - 1452-8630

VL - 14

SP - 775

EP - 799

JO - Applicable Analysis and Discrete Mathematics

JF - Applicable Analysis and Discrete Mathematics

IS - 3

ER -

A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this