Ipotizzando una sequenza infinita di attacchi sugli archi di un grafo, si cerca una strategia di difesa utilizzando il minor numero di guardie mobili piazzate sui nodi del grafo. La difesa avviene spostando una guardia da un vertice al suo adiacente lungo l'arco attaccato, con la possibilità di muovere anche altre guardie su vertici adiacenti al loro nodo di riferimento. Analizzando i lavori di Klostermeyer e Mynhardt prima, e di Babu et al. poi, si dipinge un quadro d'insieme su questa classe di problemi, soffermandosi in particolar modo sulle due caratterizzazioni di lower e upper bound, analizzando infine un algoritmo in tempo lineare per una specifica classe di grafi.
Trasversale eterno
BOGANI, LUCA
2021/2022
Abstract
Ipotizzando una sequenza infinita di attacchi sugli archi di un grafo, si cerca una strategia di difesa utilizzando il minor numero di guardie mobili piazzate sui nodi del grafo. La difesa avviene spostando una guardia da un vertice al suo adiacente lungo l'arco attaccato, con la possibilità di muovere anche altre guardie su vertici adiacenti al loro nodo di riferimento. Analizzando i lavori di Klostermeyer e Mynhardt prima, e di Babu et al. poi, si dipinge un quadro d'insieme su questa classe di problemi, soffermandosi in particolar modo sulle due caratterizzazioni di lower e upper bound, analizzando infine un algoritmo in tempo lineare per una specifica classe di grafi.File | Dimensione | Formato | |
---|---|---|---|
Bogani_Luca.pdf
accesso aperto
Dimensione
410.65 kB
Formato
Adobe PDF
|
410.65 kB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/42078