Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 30, Number 4, 1996
Page(s) 305 - 318
DOI https://doi.org/10.1051/ita/1996300403051
Published online 01 February 2017
  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. [MR: 1130319] [Zbl: 0751.68042] [Google Scholar]
  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. [Zbl: 0876.68080] [MR: 1286265] [Google Scholar]
  3. 3. A. BLUM, Some tools for approximate 3-coloring, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990. [Google Scholar]
  4. 4. B. BOLLOBAS, Random graphs, Academic Press, 1985. [MR: 809996] [Zbl: 0567.05042] [Google Scholar]
  5. 5. G. Dr BATTISTA and R. TAMASSIA, Incremental planarity testing", Proc. 30th Annual Symp. on Fundations of Computer Science, 1989. [Google Scholar]
  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. [Zbl: 0765.68024] [Google Scholar]
  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. [Google Scholar]
  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. [Zbl: 0977.68560] [Google Scholar]
  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. [Zbl: 0800.68627] [Google Scholar]
  10. 10. P. ERDÖS and A. RÈNYI, On random graphs I, Publ. Math. Debrecen, 6, pp.290-297. [MR: 120167] [Zbl: 0092.15705] [Google Scholar]
  11. 11. S. EVEN and H. GAZIT, Updating distances in dynamic graphs, Methods of Operations Research, 49, 1985. [MR: 816974] [Zbl: 0565.05052] [Google Scholar]
  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. [Google Scholar]
  13. 13. Z. GALIL and G. F. ITALIANO, Reducing edge connectivity to vertex connectivity, SIGACT News, 1991, 22 (1), pp. 57-61. [MR: 1202856] [Google Scholar]
  14. 14. R. M. KARP, The transitive closure of a random digraph, Technical Report 89-047, International Computer Science Institutive (ICSI), August 1989. [Zbl: 0712.68076] [MR: 1068492] [Google Scholar]
  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. [Zbl: 0463.68060] [MR: 604871] [Google Scholar]
  16. 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] [Google Scholar]
  17. 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] [Google Scholar]
  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. [Google Scholar]
  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. [MR: 1018396] [Zbl: 0662.68071] [Google Scholar]
  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. [Google Scholar]
  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. [MR: 786890] [Zbl: 0568.68050] [Google Scholar]
  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. [Zbl: 0612.94004] [Google Scholar]
  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. [Zbl: 0632.68043] [Google Scholar]
  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. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.