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

How to cite

top

Alimonti, 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. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.