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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.