ArchivIA Università degli Studi di Catania
 

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

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10761/1560

Data: 26-feb-2014
Autori: Nolassi, Salvatore Mario
Titolo: 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.
InArea 01 - Scienze matematiche e informatiche

Full text:

File Descrizione DimensioniFormatoConsultabilità
NLSSVT80M16C351B-NolassiThesis.pdfNolassi-PhdDissertation1,47 MBAdobe PDFVisualizza/apri


Tutti i documenti archiviati in ArchivIA sono protetti da copyright. Tutti i diritti riservati.


Segnala questo record su
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.