Finding a minimal dominating set of a graph combining various heuristic approaches based on Variable Neighborhood Search

Abstract

Many complex combinatorial optimization problems cannot be solved by traditional optimization techniques. Therefore, these types of problems often require the application and sometimes a combination of other scientific approaches to obtain, at the very least, adequate solutions. As demonstrated in numerous papers, heuristic approaches are usually more efficient and effective compared to classical methods, especially in managing neighboring uncertainty. Therefore, this paper focuses on combining various heuristic approaches based on the basic variable neighborhood search (BVNS) metaheuristic. This paper aims to find a minimal dominating set of a graph, which is a well-known NP-complete problem.