Heuristics for the weighted total domination problem

Alejandra Casado (), Jesús Sánchez-Oro () and Anna Martínez-Gavara ()
Additional contact information
Alejandra Casado: Universidad Rey Juan Carlos
Jesús Sánchez-Oro: Universidad Rey Juan Carlos
Anna Martínez-Gavara: Universitat de València

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2025, vol. 33, issue 2, No 9, 395-436

Abstract: Abstract The weighted total domination problem (WTDP) belongs to the family of dominating set problems. Given an edge- and vertex- weighted graph, the WTDP consists in selecting a total dominating set D, such that the sum of vertices and edges weights of the subgraph induced by D plus, for each vertex not in D, the minimum weight of its edge to a vertex in D is minimized. A total dominating set D is a subset of the graph’s vertices, such that every vertex, including those in D, is at least adjacent to one vertex in D. This problem arises in many real-life applications closely related to covering and independent set problems; however, it remains computationally challenging due to its $$\mathcal{N}\mathcal{P}$$ N P -hardness. This work presents a variable neighborhood search (VNS) procedure to tackle the WTDP, and investigates the advantages and disadvantages of a multi-start strategy within VNS methodology. In addition, we develop a biased greedy randomized adaptive search procedure (Biased GRASP) that keeps adding elements once a feasible solution is found to produce high-quality initial solutions. We perform extensive numerical analysis to look into the influences of the algorithmic components and to disclose the contribution of the elements and strategies of our method. Finally, the empirical analysis shows that our proposal outperforms the state-of-art results, and the statistical analysis confirms the superiority of our proposal to find the best total dominating sets.

Keywords: Weighted total domination problem; Graph domination; Biased grasp; Variable neighborhood search; Metaheuristics; 68W99; 90B99 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-025-00695-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:33:y:2025:i:2:d:10.1007_s11750-025-00695-1

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-025-00695-1

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().