Average case analysis of fully dynamic reachability for directed graphs
Alimonti, Paola ; Leonardi, Stefano ; Marchetti-Spaccamela, Alberto
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 305-318 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@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},
     volume = {30},
     year = {1996},
     pages = {305-318},
     mrnumber = {1427937},
     zbl = {0876.68080},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 305-318. http://gdmltest.u-ga.fr/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 1130319 | Zbl 0751.68042

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 1286265

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 809996 | Zbl 0567.05042

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 0765.68024

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 0977.68560

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 0800.68627

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

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

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 1202856

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

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 604871

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

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

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 1018396 | Zbl 0662.68071

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 786890 | Zbl 0568.68050

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 0612.94004

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 0632.68043

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.