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.
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. In this paper we present an application of ant colony optimization (ACO) to the Minimum Weighted Dominating Set Problem. We introduce a heuristic for this problem that takes into account the weights of vertexes being covered and show that it is more efficient than the greedy algorithm using the standard heuristic. Further we give implementation details of ACO applied to this problem. We tested our algorithm on graphs with different sizes, edge densities, and weight distribution functions and shown that it gives greatly improved results over these acquired by the greedy algorithms.