Greedy Randomized Construction with Vertex Degree for the Minimum Independent Dominant Set Problem

The Minimum Independent Dominating Set (MIDS) problem is a classic graph theory
problem that has applications on wireless networks, wireless sensor networks and similarity sets extractions. As an exact approach to solve the problem will lead to exponential execution times, some work has been done to handle it using metaheuristics. However, these works use a customized path cost approach in the solution. In this work, we will show that using a classic information - the vertex degree - allied with a Greedy Randomized Construction metaheuristic, can lead to better
results than other works on the DIMACS and BHOSLIB benchmarks in most of the instances. We developed a new algorithm called GRC+VD to tackle the problem and we statistically test its result in comparison to other works to show that it performs better than them.