In several applications it is necessary to deal with data structures that may dinamically change during a sequence of operations. In these cases the classical worst case analysis of the cost of a single operation may not adequately describe the behaviour of the structure but it is rather more meaningful to analyze the cost of the whole sequence of operations. In this paper we first discuss some results on maintaining paths in dynamic graphs. Besides, we consider paths problems on dynamic labeled graphs and we show how to maintain path expressions in the acyclic case when insertions of new arcs are allowed.
Dynamic maintenance of paths and path expressions on graphs / Ausiello, G.; Spaccamela, A. Marchetti; Nanni, U.. - 358:(1989), pp. 1-12. (Intervento presentato al convegno 13th International Symposium on Symbolic and Algebraic Computation, ISSAC 1988 tenutosi a Rome, Italy) [10.1007/3-540-51084-2_1].
Dynamic maintenance of paths and path expressions on graphs
Ausiello, G.;Spaccamela, A. Marchetti;Nanni, U.
1989
Abstract
In several applications it is necessary to deal with data structures that may dinamically change during a sequence of operations. In these cases the classical worst case analysis of the cost of a single operation may not adequately describe the behaviour of the structure but it is rather more meaningful to analyze the cost of the whole sequence of operations. In this paper we first discuss some results on maintaining paths in dynamic graphs. Besides, we consider paths problems on dynamic labeled graphs and we show how to maintain path expressions in the acyclic case when insertions of new arcs are allowed.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.