Abstract
Given an undirected graph G(V,E), the minimum total dominating set (MTDS) problem consists of finding a subset \(D \subseteq V\) with the minimum vertices such that every vertex v ∈ V is adjacent to at least one vertex in D. That is, even for the vertices in D there should at least one neighbor in D. In this paper, we develop an efficient local search framework called LS_DTR to solve MTDS, which is with dynamic scoring function, tabu combined with configuration check, and balanced random walk. Firstly, a dynamic scoring function is presented to guide the search towards the promising solution space. Subsequently, the TaCC2 strategy combining tabu with two-level configuration checking is implemented to avoid visiting solutions repeatedly. Further, the balanced random walk strategy is applied to introduce the diversity into the search. Based on the three components, an efficient vertex selecting strategy is proposed. Finally, the vertex selecting strategy is applied to select the vertex to perform the remove or add operator during the local search. We use the commercial exact solver as the baseline and compare with the-state-of-art algorithm. Meanwhile, in order to verify the effectiveness of LS_DTR, we not only test on the DIMACS instances, but also extend the benchmark to the random general graphs and unit disk graphs. The results show that our algorithm LS_DTR outperforms the other algorithms on most instances.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Gary MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. J Assoc Comput 3(23):555–565
Aoun B, Boutaba R, Iraqi Y, Kenward G (2006) Gateway placement optimization in wireless mesh networks with qos constraints. IEEE J Sel Areas Commun 24(11):2127–2136
Belhoul Y, Yahiaoui S, Kheddouci H (2014) Efficient self-stabilizing algorithms for minimal total k-dominating sets in graphs. Inf Process Lett 114(7):339–343
Akkaya K, Younis M (2005) A survey on routing protocols for wireless sensor networks. Ad hoc Netw 3(3):325–349
Balaji S, Kannan K, Venkatakrishnan YB (2013) Total dominating set based algorithm for connected dominating set in ad hoc wireless networks. WSEAS Trans Math 12(12):1164–1172
Cockayne EJ, Dawes RM, Hedetniemi ST (1980) Total domination in graphs. Networks 10 (3):211–219
Henning MA (2009) A survey of selected recent results on total domination in graphs. Discret Math 309(1):32–63
Zhu J (2009) Approximation for minimum total dominating set. In: Proceedings of the 2nd international conference on interaction sciences: information technology, culture and human, ACM, 2009:119–124
Sasireka A, Muthuraj R (2018) Total domination on anti fuzzy graph. New Trends Math Sci 4(6):28–39
Yuan F, Li C, Gao X, Yin M, Wang Y (2019) (2019). A novel hybrid algorithm for minimum total dominating set problem. Mathematics 7(3):222
Smith DH, Montemanni R, Perkins S (2020) The use of an exact algorithm within a tabu search maximum clique algorithm. Algorithms 13(10):253
Gao J, Chen J, Yin M, Chen R, Wang Y (2018) An exact algorithm for maximum k-Plexes in massive graphs. International Joint Conference on Artificial Intelligence
Wang Y, Cai S, Pan S, Li X, Yin M (2020) Reduction and local search for weighted graph coloring problem. National Conference on Artificial Intelligence
Luo C, Hoos HH, Cai S, Lin Q, Zhang H, Zhang D (2019) Local search with efficient automatic configuration for minimum vertex cover. International Joint Conference on Artificial Intelligence
Chen P, Wan H, Cai S, Li J, Chen H (2020) Local search with dynamic-threshold configuration checking and incremental neighborhood updating for maximum k-plex problem. National Conference on Artificial Intelligence
AlKasem HH, Menai MEB (2020) Stochastic local search for partial Max-SAT: an experimental evaluation. Artif Intell Rev 1–42. https://doi.org/10.1007/s10462-020-09908-4
Wang Y, Cai S, Chen J, Yin M (2018) A fast local search algorithm for minimum weight dominating set problem on massive graphs. International Joint Conference on Artificial Intelligence
Cai S, Su K, Luo C, Sattar A (2013) NuMVC: an efficient local search algorithm for minimum vertex cover. J Artif Intell Res 46(1):687–716
Luo C, Cai S, Su K, Huang W (2017) CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability. Artif Intell 2017(2):26–44
Houck CR, Joines JA, Kay MG (1996) Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems. Comput Oper Res 23(6):587– 596
Harrabi O, Chaouachi J (2020) Towards effective resolution approaches for solving the sum coloring problem. J Exp Theor Artif Intell 32(1):31–57
Glover F (1989) Tabu search—part II. Informs J Comput 1(3):190–206
Escobar JW, Linfati R, Toth P, Baldoquin MG (2014) A hybrid granular Tabu search algorithm for the multi-depot vehicle routing problem. J Heuristics 20(5):483–509
Chalupa D (2018) On transitions in the behaviour of tabu search algorithm TabuCol for graph colouring. J Exp Theor Artif Intell 30(1):53–69
Dokeroglu T, Sevinc E, Cosar A (2019) Artificial bee colony optimization for the quadratic assignment problem. Appl Soft Comput 76:595–606
Arito F, Leguizamón G (2009) Incorporating tabu search principles into aco algorithms, Springer, Berlin
Abdel-Basset M, Manogaran G, El-Shahat D, Mirjalili S (2018) Integrating the whale algorithm with tabu search for quadratic assignment problem: a new approach for locating hospital departments. Applied Soft Computing 73:530–546
Li X, Zhu L, Baki F, Chaouch AB (2018) Tabu search and iterated local search for the cyclic bottleneck assignment problem. Comput Oper Res 96:120–130
Cai S, Su K (2011) Local search with configuration checking for SAT. International Conference on Tools with Artificial Intelligence
Luo C, Cai S, Wu W, Su K (2013) Focused random walk with configuration checking and break minimum for satisfiability. Principles and Practice of Constraint Programming
Wang Y, Yin M, Ouyang D, Zhang L (2017) A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem. Int Trans Oper Res 24(6):1463– 1485
Wang Y, Cai S, Yin M (2017) Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. J Artif Intell Res 2017(58):267–295
Hu S, Li R, Zhao P, Yin M (2018) A hybrid metaheuristic algorithm for generalized vertex cover problem. Memetic Comput 10(2):165–176
Li R, Cai S, Hu S, Yin M, Gao J (2018) NuMWVC: A novel local search for minimum weighted vertex cover problem. National Conference on Artificial Intelligence
Pullan W, Hoos HH (2006) Dynamic local search for the maximum clique problem. J Artif Intell Res 25(1):159–185
Friedrich T, He J, Hebbinghaus N, Neumann F, Witt C (2009) Analyses of simple hybrid algorithms for the vertex cover problem. Evol Comput 17(1):3–19
Fan Y, Li N, Li C, Ma Z, Latecki LJ, Su K (2017) Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In: Proceedings of the 26th international joint conference on artificial intelligence, pp 622–630
Parkes AJ (2002) Scaling properties of pure random walk on random 3-SAT. Principles and Practice of Constraint Programming
Mastrogiovanni M (2007) The clustering simulation framework: a simple Manual. 〈 http://www.michele-mastrogiovanni.net/software/download/README.pdf〉
Jovanovic R, Tuba M, SimianD (2010) Ant colony optimization applied to minimum weight dominating set problem. The 12th WSEAS International Conference on Automatic Control, Modelling and Simulation (ACMOS’10)
Acknowledgements
This work is supported by the project of the Fundamental Research Funds for the Central Universities under Grant No.2412020QD008, Jilin education department 13th five-year science and technology project under Grant Nos.JJKH20190726KJ, JJKH20190756SK and the National Natural Science Foundation of China (NSFC) under Grant No.61806082, 61976050.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Hu, S., Liu, H., Wang, Y. et al. Towards efficient local search for the minimum total dominating set problem. Appl Intell 51, 8753–8767 (2021). https://doi.org/10.1007/s10489-021-02305-6
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-021-02305-6