ArchivIA Università degli Studi di Catania
 

ArchivIA - Archivio istituzionale dell'Universita' di Catania >
Tesi >
Tesi di dottorato >
Area 01 - Scienze matematiche e informatiche >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10761/1560

Issue Date: 26-Feb-2014
Authors: Nolassi, Salvatore Mario
Title: Algoritmi euristici per il Problema della Dominazione Romana
Abstract: 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.
Appears in Collections:Area 01 - Scienze matematiche e informatiche

Files in This Item:

File Description SizeFormatVisibility
NLSSVT80M16C351B-NolassiThesis.pdfNolassi-PhdDissertation1,47 MBAdobe PDFView/Open


Items in ArchivIA are protected by copyright, with all rights reserved, unless otherwise indicated.


Share this record
Del.icio.us

Citeulike

Connotea

Facebook

Stumble it!

reddit


 

  Browser supportati Firefox 3+, Internet Explorer 7+, Google Chrome, Safari

ICT Support, development & maintenance are provided by the AePIC team @ CILEA. Powered on DSpace Software.