Pagina Radice del Progetto: Algoritmo Casualizzato Lineare per lo Spanning Tree

Dato un grafo (semplice e non orientato) G=(V,E), un albero ricoprente è un insieme T di archi di G che non includa cicli e che offra un percorso tra ogni coppia di nodi. Siano dati inoltre dei pesi sugli archi di G, vogliamo trovare un albero ricoprente di peso minimo (Il peso di un albero T resta definito come somma dei pesi degli archi di T). Nel fare ciò vogliamo impiegare un numero di passi che sia al più lineare nel numero di archi di G. Allo stato di conoscenze attuali, resta obbligata la scelta di un algoritmo randomizzato (di tipo Las Vegas).

È un progetto assai ambizioso, basato sul risultato esposto in:

Karger, David R.; Klein, Philip N.; Tarjan, Robert E.
A randomized linear-time algorithm to find minimum spanning trees.
J. Assoc. Comput. Mach. 42 (1995), no. 2, 321--328.

La brevità e semplicità di tale aticolo non tragga in inganno. È necessario infatti includere come black-box l'algoritmo descritto nel seguente articolo.

Dixon, Brandon; Rauch, Monika; Tarjan, Robert E.
Verification and sensitivity analysis of minimum spanning trees in linear time.
SIAM J. Comput. 21 (1992), no. 6, 1184--1192

E questo secondo articolo è più ostico del precedente.

created: 25 Aprile 2001
updated: 25 Aprile 2001