Average case analysis of fully dynamic reachability for directed graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 4, pp. 305-318. 
@article{ITA_1996__30_4_305_0,
     author = {Alimonti, Paola and Leonardi, Stefano and Marchetti-Spaccamela, Alberto},
     title = {Average case analysis of fully dynamic reachability for directed graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {305--318},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {4},
     year = {1996},
     mrnumber = {1427937},
     zbl = {0876.68080},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1996__30_4_305_0/}
}
TY  - JOUR
AU  - Alimonti, Paola
AU  - Leonardi, Stefano
AU  - Marchetti-Spaccamela, Alberto
TI  - Average case analysis of fully dynamic reachability for directed graphs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 305
EP  - 318
VL  - 30
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_4_305_0/
LA  - en
ID  - ITA_1996__30_4_305_0
ER  - 
%0 Journal Article
%A Alimonti, Paola
%A Leonardi, Stefano
%A Marchetti-Spaccamela, Alberto
%T Average case analysis of fully dynamic reachability for directed graphs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 305-318
%V 30
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1996__30_4_305_0/
%G en
%F ITA_1996__30_4_305_0
Alimonti, Paola; Leonardi, Stefano; Marchetti-Spaccamela, Alberto. Average case analysis of fully dynamic reachability for directed graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 4, pp. 305-318. http://www.numdam.org/item/ITA_1996__30_4_305_0/

1. G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela and U. Nanni, Incremental algorithms for minimal length paths. J. of Algorithms, 1991, 12, pp. 615-638. | MR | Zbl

2. P. Alimonti, S. Leonardi, A. Marchetti-Spaccamela and X. Messeguer, Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs, Proc. 19th Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, Springer-Verlag, 1993. | MR

3. A. Blum, Some tools for approximate 3-coloring, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990.

4. B. Bollobas, Random graphs, Academic Press, 1985. | MR | Zbl

5. G. Dr Battista and R. Tamassia, Incremental planarity testing", Proc. 30th Annual Symp. on Fundations of Computer Science, 1989.

6. G. Dr Battista and R. Tamassia, On-line graph algorithms with SPQR-trees, Proc. 17th Int. Coll. on Automata, Languages and Programming, LNCS, Springer-Verlag, 1990. | Zbl

7. D. Eppstein, Z. Galil and G. F. Italiano, Improved Sparsification, Technical Report, 93-20, Department of Information andComputer Science, University of California, Irvine, 1993.

8. D. Eppstein, Z. Galil, G. F. Italiano and A. Nissenzweig, Sparsification - A technique for speeding updynamic graph algorithms, Proc. 33rd Annual Symp. on Foundations of Computer Science, 1992. | Zbl

9. D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook and M. Young, Maintenance of a minimum spanning forest in a dynamic planar graph, Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, S. Francisco, 1990. | Zbl

10. P. Erdös and A. Rènyi, On random graphs I, Publ. Math. Debrecen, 6, pp.290-297. | MR | Zbl

11. S. Even and H. Gazit, Updating distances in dynamic graphs, Methods of Operations Research, 49, 1985. | MR | Zbl

12. Z. Galil and G. F. Italiano, Fully dynamic algorithms for edge-connectivity problems, Proc. 23rd ACM Symp. on Theory of Comp., 1991, pp.317-327.

13. Z. Galil and G. F. Italiano, Reducing edge connectivity to vertex connectivity, SIGACT News, 1991, 22 (1), pp. 57-61. | MR

14. R. M. Karp, The transitive closure of a random digraph, Technical Report 89-047, International Computer Science Institutive (ICSI), August 1989. | MR

15. R. M. Karp and R. E. Tarjan, Linear expected-time algorithms for connectivity problems, Proc. of the 11th. annual ACM Symp. on Theory of Computing, 1980. pp. 368-377. | MR

16. G. F. Italiano, Amortized efficiency of a path retriaval data structure, Theoret. Comp. Sri., 1986, 48, pp. 273-281. | MR | Zbl

17. G. F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Inf. Proc. Lett, 28, 1988, pp.5-11. | MR | Zbl

18. J. A. La Poutré, Maintenance of triconnected components of graphs, Proc. 19th Int. Coll. Automata Languages and Programming, Lect. Not. in Computer Sci., Springer-Verlag, 1992, pp.354-365.

19. J. A. La Poutré and J. Van Leeuwen, Maintenance of transitive closure and transitive reduction of graphs, Proc. Work, on Graph Theoretic concepts in Comp. Sci., LNCS 314 Springer-Verlag, Berlin, 1985, pp. 106-120. | MR | Zbl

20. J. H. Reif, P. G. Spirakis and M. Yung, Re-randomization and average case analysis of fully dynamic graph algorithms, Alcom Technical Report ALCOM-LT-054, 1994.

21. H. Rohnert, A dynamization of the all-pairs least cost path problem, Proc. of the 2nd Symp. on Theoretical Aspects of Computer Science, LNCS 182, Springer-Verlag, 1990. | MR | Zbl

22. M. Santha and U. V. Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and Systems Science, 1986, 33, pp.75-87. | Zbl

23. R. E. Tarjan and Jan Van Leeuwen, Worst case analysis of set union algorithms, Journal of Assoc. Comput. Mach., 1984, 31, pp. 245-281. | Zbl

24. J. Westbrook, Algorithms and data structures for dynamic graph problems, Ph. D. Dissertation, Tech. Rep., CS-TR-229-89, Dept. Of Computer Science, Princeton University, 1989.