Swarm intelligence, exact and matheuristic approaches for minimum weight directed dominating set problem. (March 2022)

• Record Type: Journal Article
• Authors: Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André
• Is Part Of: Engineering applications of artificial intelligence. Volume 109(2022)
• Publication Date: 2022-03
• Subjects: Directed dominating set -- Minimum weight directed dominating set -- Artificial bee colony algorithm -- Invasive weed optimization algorithm -- Swarm intelligence -- Matheuristic; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2021.104647
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: There exist numerous heuristic and exact approaches in the literature for addressing minimum weight dominating set problem (MWDS) on vertex-weighted undirected graphs which is a well known NP -hard problem. However, little attention has been paid to its counterpart in vertex-weighted directed graphs called minimum weight directed dominating set problem (MWDDS) despite its use in modeling real-world applications involving directed interactions. As directed graphs can model undirected graphs, MWDDS can be considered as a generalization of MWDS, and hence, MWDDS is also NP -hard. In this paper, we present two approaches based on swarm intelligence, one approach based on integer linear programming (ILP) and one matheuristic approach to address the MWDDS. These approaches are the first approaches for MWDDS in their respective categories. One of our swarm intelligence approach is based on artificial be colony (ABC) algorithm, whereas the other is based on invasive weed optimization (IWO) algorithm. Both these approaches are hybridized with problem specific heuristics and a local search mechanism. We have evaluated the performance of our approaches on benchmark instances derived from the standard benchmark instances of MWDS. Computational results show the effectiveness of our approaches.