PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Mercatanti M., Bastianini G. La ricerca del cammino minimo nei grafi di grandi dimensioni e debolmente connessi. Internal note IEI-B78-12, 1978.
 
 
Abstract
(English)
No abstract available
Abstract
(Italiano)
RIASSUNTO La ricerca ricorrente dei cammini minimi fra due vertici, in un grafo di grandi dimensioni e debolmente connesso,implica tempi lunghissimi di esecuzione o,in alternativa,un esorbitante impegno di memoria,se tutti i possibili šammini sono preventivamente calcolati e utilizzati di volta in volta. Il procedimento di calcolo,di cui si tratta,rende possibile una sensibile economia di tempo, o di memoria ,rispettivamente, nell'uno o nell'altro caso. Esso presuppone il preventivo riconoscimento nel grafo di parti 'debolmente 'connesse fra loro (per es. grafi rappresentativi di aeroporti, di reti ferroviarie internazionali, ecc.) e la loro suddivisione in sottografi. Il procedimento prevede una ridistribuzione dei vertici e degli spigoli in modo tale che i "sottografi" acquisiscano la proprietÓ che i cammini minimi fra i vertici di ognuno siano minimi in assoluto,cioŔ coincidano con i cammini minimi calcolati nell'intero grafo. Il calcolo dei cammini minimi fra due vertici qualsiasi risulta pi¨ rapido per le proprietÓ che conseguono dalla suddivisione del grafo nei "sottografi" sopra specificati.
Subject grafi
G. Mathematics of Computing


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional