Can I read Exact and Heuristic Algorithms for the Weighted Total Domination Problem on EtoBox?

Exact and Heuristic Algorithms for the Weighted Total Domination Problem by Álvarez-Miranda, Eduardo; Sinnl, Markus is a scholarly article available to read on EtoBox.

What is Exact and Heuristic Algorithms for the Weighted Total Domination Problem about?

Dominating set problems are among the most important class of combinatorial problems in graph optimization, from a theoretical as well as from a practical point of view. In this paper, we address the recently introduced (minimum) weighted total domination problem. In this problem, we are given an undirected graph with a vertex weight function and an edge weight function. The goal is to find a total dominating set D in this graph with minimal weight. A total dominating set D is a subset of the vertices such that every vertex in the graph, including vertices in D, is adjacent to a vertex in D. The weight is measured as the sum of all vertex weights of vertices in D, plus the edge weights in the subgraph induced by D, plus for each vertex not in D the minimum weight of an edge from it to a vertex in D. In this paper, we present two new Mixed-Integer Programming models for the problem, and design solution frameworks based on them. These solution frameworks also include valid inequalities, starting heuristics and primal heuristics. In addition, we also develop a genetic algorithm, which is based on a greedy randomized adaptive search procedure version of our starting heuristic. We carry

Author

Álvarez-Miranda, Eduardo; Sinnl, Markus

Published

2019

Language

EN