# An Order-based Algorithm for Minimum Dominating Set with Application in Graph Mining

arXiv: https://arxiv.org/abs/1705.00318 · HTML: https://mlsanity.com/paper/1705.00318/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2017.

## Built on by (most cited first, 2 of 2)

- [A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem](https://mlsanity.com/paper/2307.16815/) (2023)
- [Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks](https://mlsanity.com/paper/2306.03434/) (2023)

## Abstract (arXiv)

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