Abstract Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o ) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.
This pheromone update rule has originally been used in an ant colony optimisation algorithm for the leaf-constrained minimum spanning tree problem @cite_7 . In this formula, @math is the best dominating set size for the current iteration and @math is the best dominating set size found so far. In ACO-LS, the values of parameters @math and @math were @math and @math @cite_42 . Hence, the vertices used in previously constructed dominating sets will be more likely to occur in the next dominating sets.
@cite_42 @cite_7
43777471 2088797223
Minimum dominating set, which is an NP-hard problem, finds many practical uses in diverse domains. A greedy algorithm to compute the minimum dominating set is proven to be the optimal approximate algorithm unless P=NP. Meta-heuristics, generally, find solutions better than simple greedy approximate algorithms as they explore the search space better without incurring the cost of an exponential algorithm. However, there are hardly any studies of application of meta-heuristic techniques for this problem. In some applications it is important to minimize the dominating set as much as possible to reduce cost and or time to perform other operations based on the dominating set. In this paper, we propose a hybrid genetic algorithm and an ant-colony optimization (ACO) algorithm enhanced with local search. We compare the performance of these two hybrid algorithms against the solutions obtained using the greedy heuristic and another hybrid genetic algorithm proposed in literature. We find that the ACO algorithm enhanced with a minimization heuristic performs better than all other algorithms in almost all instances. Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a spanning tree of the graph with smallest weight among all spanning trees of the graph, which contains at least l leaves. In this paper we have proposed two new metaheuristic approaches for the LCMST problem. One is an ant-colony optimization (ACO) algorithm, whereas the other is a tabu search based algorithm. Similar to a previously proposed genetic algorithm, these metaheuristic approaches also use the subset coding that represents a leaf-constrained spanning tree by the set of its interior vertices. Our new approaches perform well in comparison with two best heuristics reported in the literature for the problem — the subset-coded genetic algorithm and a greedy heuristic.