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

On-line computation of minimal and maximal length paths / Ausiello, G; Italiano, Giuseppe Francesco; Marchetti Spaccamela, A; Nanni, U. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 95:2(1992), pp. 245-261. [10.1016/0304-3975(92)90267-J]

On-line computation of minimal and maximal length paths

Italiano G;
1992

Abstract

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
1992
On-line computation of minimal and maximal length paths / Ausiello, G; Italiano, Giuseppe Francesco; Marchetti Spaccamela, A; Nanni, U. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 95:2(1992), pp. 245-261. [10.1016/0304-3975(92)90267-J]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/191464
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact