Fixed Set Search Applied to the Maximum Disjoint Dominating Sets Problem

被引：0

作者：

Jovanovic, Raka ^{[1
]}

Voss, Stefan ^{[2
]}

机构：

[1] Hamad Bin Khalifa Univ, Qatar Environm & Energy Res Inst QEERI, POB 5825, Doha, Qatar

[2] Univ Hamburg, Inst Informat Syst, Von Melle Pk 5, D-20146 Hamburg, Germany

来源：

METAHEURISTICS, MIC 2024, PT II | 2024年 / 14754卷

关键词：

Metaheuristic; Dominating Set; Fixed Set Search;

D O I：

10.1007/978-3-031-62922-8_26

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper the fixed set search (FSS), a population-based metaheuristic, is applied to the Maximum Disjoint Dominating Sets Problem (MDDSP). Initially, a greedy randomized adaptive search procedure (GRASP) is developed to solve the MDDSP. Subsequently, the FSS enhances GRASP by incorporating a learning mechanism that identifies common elements in high-quality solutions. Computational experiments show that the proposed method significantly outperforms current state-of-the-art methods.

引用

页码：347 / 353

页数：7

共 6 条

[1] Wireless sensor networks: a survey
Akyildiz, IF
Su, W
Sankarasubramaniam, Y
Cayirci, E
[J]. COMPUTER NETWORKS, 2002, 38 (04) : 393 - 422
[2] A Greedy Heuristic for Maximizing the Lifetime of Wireless Sensor Networks Based on Disjoint Weighted Dominating Sets
Balbal, Samir
Bouamama, Salim
Blum, Christian
[J]. ALGORITHMS, 2021, 14 (06)
[3] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
FEO, TA
RESENDE, MGC
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) : 109 - 133
[4] Fixed set search applied to the clique partitioning problem
Jovanovic, Raka
Sanfilippo, Antonio P.
Voss, Stefan
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 309 (01) : 65 - 81
[5] Mesbahi M, 2010, GRAPH THEORETIC METHODS IN MULTIAGENT NETWORKS, P362
[6] Multi-constructor CMSA for the maximum disjoint dominating sets problem
Rosati, Roberto Maria
Bouamama, Salim
Blum, Christian
[J]. COMPUTERS & OPERATIONS RESEARCH, 2024, 161

← 1 →