Record link: 
http://hdl.handle.net/20.500.12708/225335
-
Title: 
Tackling the α-Domination Problem Heuristically
en
Citation: 
Iurlano, E., Varga, J., & Raidl, G. R. (2025). Tackling the α-Domination Problem Heuristically. In A. Quesada-Arencibia, M. Affenzeller, & R. Moreno-Díaz (Eds.), Computer Aided Systems Theory : EUROCAST 2024 : 19th International Conference, Revised Selected Papers, Part I (pp. 148–156). Springer. https://doi.org/10.1007/978-3-031-82949-9_14
-
Publisher DOI: 
10.1007/978-3-031-82949-9_14
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Iurlano, Enrico 
Varga, Johannes 
Raidl, Günther R. 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Computer Aided Systems Theory : EUROCAST 2024 : 19th International Conference, Revised Selected Papers, Part I 
-
ISBN: 
978-3-031-82949-9
-
Volume: 
15172
-
DOI of the book: 
10.1007/978-3-031-82949-9
-
Date (published): 
2025
-
Event name: 
Computer Aided Systems Theory – EUROCAST 2024 
en
Event date: 
25-Feb-2024 - 1-Mar-2024
-
Event place: 
Las Palmas de Gran Canaria, Spain
-
Number of Pages: 
9
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Configuration checking; Domination; GRASP; Influence in social networks
en
Abstract: 
We focus on the α-domination problem, which is capable of modeling influence phenomena in social networks. It formally asks for a minimum cardinality subset of vertices of a given graph such that any vertex is either included in this subset or at least a fraction α of its neighbors is (0<α≤1). We address the search for solutions of high quality within a tight margin of computation time by designing, firstly, a Greedy Randomized Adaptive Search Procedure and, secondly, a Configuration Checking metaheuristic. The latter excels in terms of solution quality and speed and is able to outperform an integer programming formulation solved by the commercial solver Gurobi on a majority of tested instances which have thousands of vertices.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

9
checked on Jan 23, 2026

Google ScholarTM

Check