Minimum Weighted Dominating Set Problem

An iterated greedy algorithm for finding the minimum dominating set in weighted graphs

Report Bug · Request Feature

About The Project

A dominating set in a weighted graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set, and the sum of edge weights incident to the set for every vertex is at least K. The domination number is the minimum cardinality of a dominating set in the graph. The problem of finding the minimum weighted dominating set is a combinatorial optimization problem that has been proved to be N P-hard. Given the difficulty of this problem, an Iterated Greedy algorithm is proposed for its solution and it is compared to the solution given by an exact algorithm and by the state-of-art algorithms. Computational results show that the proposal is able to find optimal or near-optimal solutions within a short computational time.

(back to top)

Built With

• Java
• Maven

(back to top)

Getting Started

Prerequisites

To run and test this project locally, you must have Maven, Java 19 and Git installed.

Installation

1. Clone the repo:

   git clone https://github.com/joszamama/dominating-set.git

2. Install the Maven dependencies:

   cd dominating-set
   mvn clean compile

(back to top)

License

Distributed under the EPL-2.0 license. See LICENSE.md for more information.

(back to top)