We consider the problem of maintaining minimum length paths in a directed graph G=(V,E) with n nodes while inserting new arcs. A data structure which supports the following operations is presented: an add operation, which inserts an arc in the digraph, and a minpath operation, which returns a minimal length path between a pair of nodes. The data structure supports each minpath operation in O(k) worst case time, where k
Titolo: | On-line computation of minimal and maximal length paths |
Autori: | |
Data di pubblicazione: | 1992 |
Rivista: | |
Handle: | http://hdl.handle.net/11385/191464 |
Appare nelle tipologie: | 01.1 - Articolo su rivista (Article) |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.