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.
1989
13th International Symposium on Symbolic and Algebraic Computation, ISSAC 1988
Theoretical Computer Science; Computer Science (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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].
File allegati a 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1205030
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 3
social impact