Heuristics for the weighted total domination problem

• Alejandra Casado ^[1] ; Jesús Sánchez-Oro ^[1] ; Anna Martínez-Gavara ^[2]
  1. [1] Universidad Rey Juan Carlos

     Universidad Rey Juan Carlos

     Madrid, España

     
  2. [2] Universitat de València

     Universitat de València

     Valencia, España

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 395-436
• Idioma: inglés
• DOI: 10.1007/s11750-025-00695-1
• Enlaces
  • Texto completo
• Resumen

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

• Referencias bibliográficas
  • Álvarez-Miranda E, Sinnl M (2021) Exact and heuristic algorithms for the weighted total domination problem. Comput Oper Res 127:105157
  • Bai X, Zhao D, Bai S, Wang Q, Li W, Mu D (2020) Minimum connected dominating sets in heterogeneous 3d wireless ad hoc networks. Ad Hoc Netw...
  • Balakrishnan R, Ranganathan K (2012) A textbook of graph theory. Springer, Berlin
  • Beasley JE (1987) An algorithm for set covering problem. Eur J Oper Res 31:85–93
  • Beasley JE, Chu PC (1996) A genetic algorithm for the set covering problem. Eur J Oper Res 94:392–404
  • Berge C (1962) The theory of graphs and its applications. Methuen & co. Ltd, London
  • Bresina JL (1996) Heuristic-biased stochastic sampling. AAAI/IAAI 1:271–278
  • Brimberg J, Salhi S, Todosijevi´c R, Uroševi´c D (2023) Variable neighborhood search: the power of change and simplicity. Comput Oper Res...
  • Buxey G (1979) The vehicle scheduling problem and monte carlo simulation. J Oper Res Soc 30:563–573
  • Campos V, Martí R, Sánchez-Oro J, Duarte A (2014) Grasp with path relinking for the orienteering problem. J Oper Res Soc 65:1800–1813
  • Campan A, Truta TM, Beckerich M (2015) Fast dominating set algorithms for social networks. In: Midwest Artificial Intelligence and Cognitive...
  • Caprara A, Toth P, Fischetti M (2000) Algorithms for the set covering problem. Ann Oper Res 98:353–371
  • Casado A, Pérez-Peló S, Sánchez-Oro J, Duarte A (2022) A grasp algorithm with tabu search improvement for solving the maximum intersection...
  • Casado A, Bermudo S, López-Sánchez A, Sánchez-Oro J (2023) An iterated greedy algorithm for finding the minimum dominating set in graphs....
  • Casado A, Mladenovi´c N, Sánchez-Oro J, Duarte A (2023) Variable neighborhood search approach with intensified shake for monitor placement....
  • Cockayne EJ, Hedetniemi ST (1977) Towards a theory of domination in graphs. Networks 7:247–261
  • Cockayne EJ, Dawes R, Hedetniemi ST (1980) Total domination in graphs. Networks 10:211–219
  • Corcoran P, Gagarin A (2021) Heuristics for k-domination models of facility location problems in street networks. Comput Oper Res 133:105368
  • Faulin J, Juan AA (2008) The algacea-1 method for the capacitated vehicle routing problem. Int Trans Oper Res 15:599–621
  • Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71
  • Ferone D, Gruler A, Festa P, Juan AA (2019) Enhancing and extending the classical grasp framework with biased randomisation and simulation....
  • Fleszar K, Hindi KS (2004) Solving the resource-constrained project scheduling problem by a variable neighbourhood search. Eur J Oper Res...
  • Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS...
  • Goddard W, Henning MA (2013) Independent domination in graphs: a survey and recent results. Disc Math 313:839–854
  • Grasas A, Juan AA, Faulin J, De Armas J, Ramalhinho H (2017) Biased randomization of heuristics using skewed probability distributions: a...
  • Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20:374– 387
  • Hansen P, Mladenovi´c N, Brimberg J, Pérez JAM (2019) Variable neighborhood search. Springer, Berlin
  • Hansen P, Mladenovi´c N (2006) First vs. best improvement: An empirical study. Discrete Appl Math 154: 802–817. (IV ALIO/EURO Workshop on...
  • Haynes TW, Hedetniemi S, Slater P (1998) Fundamentals of domination in graphs. CRC Press, Boca Raton