Average case analysis of fully dynamic reachability for directed graphs

 Access to full text

 Full (PDF)

1. 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. Zbl0751.68042MR1130319
2. 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. Zbl0876.68080MR1286265
3. 3. A. BLUM, Some tools for approximate 3-coloring, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990. 
4. 4. B. BOLLOBAS, Random graphs, Academic Press, 1985. Zbl0567.05042MR809996
5. 5. G. Dr BATTISTA and R. TAMASSIA, Incremental planarity testing", Proc. 30th Annual Symp. on Fundations of Computer Science, 1989. 
6. 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. Zbl0765.68024
7. 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. 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. Zbl0977.68560
9. 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. Zbl0800.68627
10. 10. P. ERDÖS and A. RÈNYI, On random graphs I, Publ. Math. Debrecen, 6, pp.290-297. Zbl0092.15705MR120167
11. 11. S. EVEN and H. GAZIT, Updating distances in dynamic graphs, Methods of Operations Research, 49, 1985. Zbl0565.05052MR816974
12. 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. 13. Z. GALIL and G. F. ITALIANO, Reducing edge connectivity to vertex connectivity, SIGACT News, 1991, 22 (1), pp. 57-61. MR1202856
14. 14. R. M. KARP, The transitive closure of a random digraph, Technical Report 89-047, International Computer Science Institutive (ICSI), August 1989. Zbl0712.68076MR1068492
15. 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. Zbl0463.68060MR604871
16. 16. G. F. ITALIANO, Amortized efficiency of a path retriaval data structure, Theoret. Comp. Sri., 1986, 48, pp. 273-281. Zbl0638.68065MR895800
17. 17. G. F. ITALIANO, Finding paths and deleting edges in directed acyclic graphs, Inf. Proc. Lett, 28, 1988, pp.5-11. Zbl0663.68052MR947249
18. 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. 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. Zbl0662.68071MR1018396
20. 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. 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. Zbl0568.68050MR786890
22. 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. Zbl0612.94004
23. 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. Zbl0632.68043
24. 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.