Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Locatelli, Alberto (2017) Partizione di grafi in stelle: modelli matematici e metodi risolutivi. [Magistrali biennali]

Per questo documento il full-text online non disponibile.

Abstract

Una stella è un albero che ha al massimo un nodo di grado superiore a uno e si dice propria se ha almeno due nodi. Dato un grafo G = (V, E), con Σ(G) si indica l’insieme di tutte le partizioni π di V tali che ogni sottografo indotto da una qualunque delle componenti di π possa essere ricoperto da una stella propria. I problemi di partizione in stelle (star partition) su un grafo G = (V, E) consistono nel trovare una partizione π ∈ Σ(G) tale da minimizzare una funzione f : Σ(G) → R data. In particolare, il Minimum Star Partition Problem (problema MSP) richiede di trovare una partizione π ∈ Σ(G) tale da avere il minimo numero di componenti possibile. Si ri- corda infine che, dato un grafo G = (V, E), un sottoinsieme D ⊆ V è detto dominante se ogni nodo di V \ D è adiacente ad almeno un nodo di D. Il problema di determinare un sottoinsieme D ⊆ V dominante e di cardinalità minima è detto Minimum Dominating Set Problem (problema MDS). Lo studio affrontato in questa tesi parte dal lavoro svolto in [1], dove viene si fornisce una formulazione di programmazione lineare intera per il problema MSP e si dimostra che tale formulazione, nel caso in cui G sia un albero, risulta perfetta. Il lavoro di tesi parte dal dimostrare che il problema MSP è equivalente al problema MDS. Poiché il problema MDS è centrale in teoria dei grafi, esiste una vasta letteratura in proposito e dunque l’equivalenza trovata permette di riportare tutti i risultati validi per il problema MDS al problema MSP. Tale equivalenza non ha solo rilevanza a livello teorico, ma anche a livello pratico. Infatti si fornisce un algoritmo che, a partire da un insieme dominante di cardinalità minima ottenuto, è in grado di offrire una soluzione ottima del problema MSP. Dai test effettuati è emerso che il tempo necessario per risolvere il problema MSP tramite tale algoritmo è notevol-mente minore rispetto al tempo impiegato utilizzando le tecniche proposte in [1]. Si presenta poi un algoritmo che, dato un sottoinsieme dominante D ⊆ V , non necessariamente di cardinalità minima, fornisce una partizione π ∈ Σ(G) in stelle proprie tale che |π| ≤ |D|. Tale algoritmo si rivela di grande utilità poiché consente di utilizzare le numerose euristiche per risolvere il problema MDS reperibili in letteratura al fine di risolvere il problema MSP. In questa tesi si vuole inoltre generalizzare il concetto di partizione in stelle di un grafo. In particolare, una volta assegnato ad ogni sottografo di G di tipo stella un peso, si vuole trovare una famiglia di sottografi di G di tipo stella la cui somma dei pesi sia minima e tale che gli insiemi dei loro vertici formi una partizione π ∈ Σ(G). Questo problema è detto Weighted Minimum Star Partition Problem (problema WMSP). Partendo dai modelli proposti in [1] e ideati per formulare il problema MSP, si forniscono del- le formulazioni di programmazione lineare intera che descrivono il problema WMSP . Si analizzano inoltre alcune proprietà dei poliedri relativi ai modelli di programmazione lineare intera per la formulazione del problema WMSP introdotti. In particolare si determina la loro dimensione nel caso dei grafi completi e, nel caso di alberi, si trova un limite superiore alla dimensione del poliedro. Si introduce quindi la famiglia di disuguaglianze I atte a migliorare le formulazioni del problema WMSP proposte. Si dimostra che le diseguaglianze in I sono soddisfatte da tutte le soluzioni intere del problema WMSP e si forniscono alcuni semplici esempi nei quali l’aggiunta di tali di- seguaglianze migliora le formulazioni date. Il software PORTA ha permesso di verificare che le diseguaglianze di I introdotte, per alcuni degli esempi forniti, risultano faccette. Infine si presentano alcune sottofamiglie di Ie per due di queste si fornisce un algoritmo di separazione esatto. Alcuni degli algoritmi proposti per la risoluzione del problema MSP e del problema WMSP sono stati tradotti in programmi che sono parte integrante di questa tesi. Inoltre, qualora l’algoritmo preveda la risoluzione di problemi di programmazione lineare o programmazione lineare intera, si è utilizzato IBM ILOG CPLEX Optimization Studio 12.6 come solver. Questi programmi sono stati testati su delle istanze di prova per analizzare il loro comportamento da un punto di vista computazionale. Con tali test si è evi- denziato che le sottofamiglie di I, per le quali si è fornito un algoritmo di separazione esatto, migliorano di poco le formulazioni dei modelli proposti. In seconda battuta è emerso che il tempo necessario per trovare una solu- zione per il problema MSP utilizzando l’algoritmo che sfrutta l’equivalenza fra il problema MSP e il problema MDS è notevolmente minore rispetto al tempo impiegato utilizzando il modello proposto in [1].

Tipologia del documento:Magistrali biennali
Settori scientifico-disciplinari del MIUR:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:56642
Relatore:De Giovanni, Luigi
Data della tesi:13 Ottobre 2017
Biblioteca:Polo di Scienze > Biblioteca di Matematica

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione e non da noi.

[1] G. Andreatta, C. De Francesco, L. De Giovanni, P. Serafini, The Cerca con Google

Constrained Star Partition Problem, Working Paper, Padova (2016). Cerca con Google

Solo per lo Staff dell Archivio: Modifica questo record