Average case analysis of fully dynamic reachability for directed graphs
Paola Alimonti; Stefano Leonardi; Alberto Marchetti-Spaccamela
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)
- Volume: 30, Issue: 4, page 305-318
- ISSN: 0988-3754
Access Full Article
topHow to cite
topAlimonti, Paola, Leonardi, Stefano, and Marchetti-Spaccamela, Alberto. "Average case analysis of fully dynamic reachability for directed graphs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.4 (1996): 305-318. <http://eudml.org/doc/92539>.
@article{Alimonti1996,
author = {Alimonti, Paola, Leonardi, Stefano, Marchetti-Spaccamela, Alberto},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {directed graph},
language = {eng},
number = {4},
pages = {305-318},
publisher = {EDP-Sciences},
title = {Average case analysis of fully dynamic reachability for directed graphs},
url = {http://eudml.org/doc/92539},
volume = {30},
year = {1996},
}
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
PB - EDP-Sciences
VL - 30
IS - 4
SP - 305
EP - 318
LA - eng
KW - directed graph
UR - http://eudml.org/doc/92539
ER -
References
top- 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. 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. 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. Zbl0567.05042MR809996
- 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. Zbl0765.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. Zbl0977.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. Zbl0800.68627
- 10. P. ERDÖS and A. RÈNYI, On random graphs I, Publ. Math. Debrecen, 6, pp.290-297. Zbl0092.15705MR120167
- 11. S. EVEN and H. GAZIT, Updating distances in dynamic graphs, Methods of Operations Research, 49, 1985. Zbl0565.05052MR816974
- 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. MR1202856
- 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. 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. G. F. ITALIANO, Amortized efficiency of a path retriaval data structure, Theoret. Comp. Sri., 1986, 48, pp. 273-281. Zbl0638.68065MR895800
- 17. G. F. ITALIANO, Finding paths and deleting edges in directed acyclic graphs, Inf. Proc. Lett, 28, 1988, pp.5-11. Zbl0663.68052MR947249
- 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. Zbl0662.68071MR1018396
- 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. Zbl0568.68050MR786890
- 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. 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. 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.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.