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.
It is known that the greedy approximation algorithm for vertex cover by Chv ' a tal @cite_46 can be used to find small dominating sets in polynomial time. This algorithm achieves approximation ratio @math , where @math is the maximum degree of a vertex and @math is the @math -th harmonic number. As we indicated above, @math . The application of the greedy approximation algorithm to find small dominating sets works as follows. For simplicity, we will say that a vertex @math is if @math . In the algorithm, vertices are ordered based on a value @math , which denotes the . In each iteration, vertex @math with the largest @math in partial dominating set @math is taken and put into @math . The algorithm terminates when @math is a dominating set.
@cite_46
2157054705
Let A be a binary matrix of size m × n, let cT be a positive row vector of length n and let e be the column vector, all of whose m components are ones. The set-covering problem is to minimize cTx subject to Ax ≥ e and x binary. We compare the value of the objective function at a feasible solution found by a simple greedy heuristic to the true optimum. It turns out that the ratio between the two grows at most logarithmically in the largest column sum of A. When all the components of cT are the same, our result reduces to a theorem established previously by Johnson and Lovasz.