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
Ausiello, G; Italiano, Giuseppe Francesco; Marchetti Spaccamela, A; Nanni, U. (1992). On-line computation of minimal and maximal length paths. THEORETICAL COMPUTER SCIENCE, (ISSN: 0304-3975), 95:2, 245-261. Doi: 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
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
