Algoritmi euristici per il Problema della Dominazione Romana

A Roman Dominating Function on a graph G is a function that labels the vertices of the graph with an integer between (0, 1, 2), satisfying the condition that every vertex labeled by 0 is adjacent to at least one vertex labeled by 2. The weight of a Roman Dominating Function is the sum of all the labels, and the minimum weight is called the Roman Domination Number and the Roman Domination Problem is to find such number. We first introduce the basic concepts related to the Roman domination. Then, the problem is studied for two particular class of graphs, grid graphs and bipartite graphs. For grid graphs we derive an improved lower bound and define some general schemas to produce a good coverings for the Roman Domination Problem over grid graphs. In addition, we present an upper bound on the Roman Domination Number which improves the previous. Regarding the bipartite graphs we propose a simple approach that use a vertex cover in order to get a function of Roman domination in polynomial time. Continuing the dissertation we present some heuristic approaches to the Roman domination. In particular, we describe a polynomial-time heuristic algorithm for computing the Roman domination number for any type of graphs class. Finally we propose some variants of the same heuristic, and some of them are then implemented on CUDA architecture which allows the parallelization of the computation on the GPU and showing the data structures used and the issues addressed.

Una funzione di Dominazione Romana su un grafo G è una funzione di copertura che assegna ai vertici del grafo uno tra i valori (0, 1, 2) con l'unico vincolo che ogni vertice con valore 0 abbia almeno un vicino con valore 2. Il peso di una funzione di Dominazione Romana è la somma di tutti i valori assegnati e il numero di Dominazione Romana di un grafo G è definito come il minimo tra tutte le funzioni di Dominazione Romana su G. Dopo un'introduzione ai concetti base che ruotano attorno alla Dominazione Romana, viene studiato il problema per due particolari classe di grafi, cioè grafi a griglia e i bipartiti. Per i grafi a griglia vengono prodotti degli schemi di copertura ottimali per griglie di qualsiasi dimensione e inoltre vengono migliorati i limiti superiori e inferiori noti del numero di Dominazione Romana. Per quanto riguarda i grafi bipartiti viene proposto un approccio che partendo da un insieme di vertex cover del grafo produce una funzione di Dominazione Romana in tempo polinomiale. Nel prosieguo della dissertazione vengono mostrati vari approcci euristici per qualsiasi classe di grafo. In particolare viene prodotto un algoritmo euristico che in tempo polinomiale calcola una copertura e un numero di Dominazione Romana che rientra nei limiti teorici noti introducendo un nuovo parametro associato ai vertici del grafo. Infine una delle varianti della stessa euristica è stata implementata su architettura CUDA permettendo la parallelizzazione del calcolo su GPU e saranno mostrate le strutture dati utilizzate e le problematiche riscontrate.