Trasversale eterno

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.