Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/339962 
Year of Publication: 
2026
Citation: 
[Journal:] Journal of Heuristics [ISSN:] 1572-9397 [Volume:] 32 [Issue:] 2 [Article No.:] 15 [Publisher:] Springer US [Place:] New York, NY [Year:] 2026
Publisher: 
Springer US, New York, NY
Abstract: 
This paper introduces a metaheuristic approach for solving the Maximum Disjoint Dominating Sets Problem (MDDSP). The problem is initially addressed using a Greedy Randomized Adaptive Search Procedure (GRASP), which incorporates two distinct local search strategies. The first employs a standard swap neighborhood, while the second utilizes a novel neighborhood structure designed to complement and enhance the effectiveness of the swap-based approach. To further improve performance, the GRASP is extended into the Fixed Set Search (FSS) metaheuristic, which integrates a learning mechanism to guide the search process. Computational experiments are conducted on various graph types, including random, Watts–Strogatz, and Barabási–Albert graphs, with up to 1,000 vertices and differing densities. The results show that the FSS significantly outperforms state-of-the-art methods, such as the multi-constructor Construct, Merge, Solve, and Adapt (CMSA) algorithm, delivering superior solution quality across nearly all test instances. The enhanced local search techniques proved particularly effective on dense graphs. Furthermore, the results confirm that the FSS consistently improves the performance of the underlying GRASP, highlighting its robustness and efficiency for solving the MDDSP.
Subjects: 
Metaheuristic
Dominating Set
Fixed Set Search
GRASP
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.