Can I read A Uniform Approach to Semi-dynamic Problems on Digraphs on EtoBox?

A Uniform Approach to Semi-dynamic Problems on Digraphs by Serafino Cicerone; Daniele Frigioni; Umberto Nanni; Francesco Pugliese is a Computer Science article available to read on EtoBox.

What is A Uniform Approach to Semi-dynamic Problems on Digraphs about?

In this paper we propose a uniform approach to deal with incremental problems on digraphs and with decremental problems on dags generalizing a technique used by La PoutrC and van Leeuwen in [ 171 for updating the transitive closure and the transitive reduction of a dag. We define a propagation property on a binary relationship over the vertices of a digraph 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 by simply setting appropriate boundary conditions. In particular, we provide semi-dynamic algorithms and data structures for maintaining a binary relationship over the vertices of a digraph (dag) with n vertices and m edges, requiring O(nmax{q,m}) total time for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of R(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n\*). We apply the proposed technique to various problems about dominance, providing a solution to the problems

Who reads A Uniform Approach to Semi-dynamic Problems on Digraphs?

Author

Serafino Cicerone; Daniele Frigioni; Umberto Nanni; Francesco Pugliese

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

1998

Language

EN

Field

Computer Science (Physical Sciences)