In this paper we generalize a technique used by La Poutré and van Leeuwen for updating the transitive closure and the transitive reduction of a dag, and propose a uniform approach to deal with semi-dynamic problems on dags. We define a propagation property on a binary relationship as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems on dags by simply setting appropriate border conditions. In particular we provide semi-dynamic algorithms and data structures for maintaining a binary relationship defined over the vertices of a dag with n vertices and m edges, requiring O(n(q + m)) total time, for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Ω(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n2). We apply the proposed technique to various problems about dominance, providing the first known incremental and decrementai solutions for maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a dag.

Counting edges in a dag / Cicerone, Serafmo; Frigioni, Daniele; Nanni, Umberto; Pugliese, Francesco. - 1197:(1997), pp. 85-100. (Intervento presentato al convegno 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1996 tenutosi a Cadenabbia (Como), Italy) [10.1007/3-540-62559-3_9].

Counting edges in a dag

Frigioni, Daniele;Nanni, Umberto;
1997

Abstract

In this paper we generalize a technique used by La Poutré and van Leeuwen for updating the transitive closure and the transitive reduction of a dag, and propose a uniform approach to deal with semi-dynamic problems on dags. We define a propagation property on a binary relationship as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems on dags by simply setting appropriate border conditions. In particular we provide semi-dynamic algorithms and data structures for maintaining a binary relationship defined over the vertices of a dag with n vertices and m edges, requiring O(n(q + m)) total time, for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Ω(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n2). We apply the proposed technique to various problems about dominance, providing the first known incremental and decrementai solutions for maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a dag.
1997
22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1996
dynamic graph algorithms, generalized graph problem, transitive closure
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Counting edges in a dag / Cicerone, Serafmo; Frigioni, Daniele; Nanni, Umberto; Pugliese, Francesco. - 1197:(1997), pp. 85-100. (Intervento presentato al convegno 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1996 tenutosi a Cadenabbia (Como), Italy) [10.1007/3-540-62559-3_9].
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/1205051
 Attenzione

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

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