An order-based algorithm for minimum dominating set with application in graph mining

作者：Chalupa David^*

来源：Information Sciences, 2018, 426: 101-116.

DOI：10.1016/j.ins.2017.10.033

• Randomised local search
• Order-based representation
• Minimum dominating set
• Complex networks
• Heuristics

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 (RLS0) 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 RLS0 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 RLS0 that is suitable for solving the minimum weight dominating set problem. The application of RLS0 in graph mining is also briefly demonstrated.

• 出版日期2018-2