## 2 Related Works
developed a new greedy algorithm to tackle the Minimum Edge Connected Dominating Set (MECDS) problem in wireless sensor networks, focusing on edge fault tolerance [32]. Their algorithm achieves an important improvement in approximation ratios and sets a new standard for constructing robust virtual backbones against link failures. [PERSON] et al. introduce a local search algorithm, DeepOpt-MWDS, for solving the Minimum Weight Dominating Set (MWDS) problem [33]. By adjusting the number of nodes added or removed based on candidate solution feedback, employing reduction rules for initial solution construction, and integrating a novel configuration checking strategy to minimize local search cycling, the algorithm outperforms existing heuristics in both efficiency and effectiveness on a wide range of graph benchmarks. That study not only demonstrates the superior performance of DeepOpt-MWDS on diverse datasets but also showcases its adaptability to other NP-hard problems, marking a contribution to the field of combinatorial optimization. In their study, [PERSON] et al. explore the polyhedral aspects of locating, open locating and locating total dominating sets within graphs, offering a fresh perspective on these variations of the classical MDS problem. By developing linear relaxations and examining their combinatorial structures, the authors successfully apply polyhedral techniques to fully describe these sets for special graph types. [PERSON] et al. introduce Adapt-CMSA, a self-adaptive variant of the Construct, Merge, Solve and Adapt (CMSA) algorithm, aimed at addressing the parameter sensitivity observed in the original CMSA algorithm [34]. By automating parameter adjustments, Adapt-CMSA reduces the need for extensive parameter tuning across different problem instances, demonstrating its effectiveness on the minimum positive influence dominating set problem (MPIDS). In their research, [PERSON] et al. propose constant-factor approximation algorithms designed to solve the MDS problem within specific subclasses of string graphs (a string graph can be defined as a graph where edges are formed by the intersections of curves, and each curve is represented by a node), with a particular emphasis on unit Bk-VPG graphs and vertically stabbed L-graphs [35]. By developing algorithms with guaranteed approximation ratios for these complex graph types, the study addresses open questions and extends previous research findings. The idea of finding a solution to the dominating set problem using centrality measures was previously proposed by [PERSON] et al. [36]. In their study, the authors applied the Shapley value centrality measures derived from game theory with a two-stage algorithm and applied them to real-world problems. Solving the MDS problem presents a perspective from the implementation of unified approximation algorithms and the introduction of novel local search strategies to the exploration of polyhedral techniques and self-adaptive algorithms; the scope of research is broad and dynamic. Each study contributes unique insights into tackling the MDS problem, whether through refining algorithmic accuracy, enhancing computational efficiency, or expanding the theoretical understanding of underlying graph structures. Notably, these efforts not only advance the state of the art in solving the MDS problem but also illustrate the adaptability of these algorithms to a spectrum of related problems and graph subclasses. The highlighted works underscore the enduring relevance of the MDS problem and the innovative approaches being developed to tackle it. Greedy algorithms, in particular, stand out for their significant contributions, demonstrating the rich potential for further research in this area. As the field progresses, it is anticipated that these foundational efforts will pave the way for even more sophisticated solutions, enhancing our ability to solve the MDS problem and its variants across increasingly complex graph structures.