Developments in Data Structure Research During the First 25 Years of FSTTCS

1. Mehta, Sahni (eds.): Handbook of Data Structures and Applications. Chapman & Hall/CRC (2005)

   Google Scholar 

2. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32, 652–686 (1985)

   Article  MATH  MathSciNet  Google Scholar 

3. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596–615 (1987)

   Article  MathSciNet  Google Scholar 

4. Tarjan, R.E.: Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods 6, 306–318 (1985)

   Article  MATH  MathSciNet  Google Scholar 

5. Bentley, J.L., Saxe, J.B.: Decomposable searching problems i: Static-to-dynamic transformation. J. Algorithms 1, 301–358 (1980)

   Article  MATH  MathSciNet  Google Scholar 

6. Overmars, M.H.: The design of dynamic data structure. In: Overmars, M. (ed.) The Design of Dynamic Data Structures. LNCS, vol. 156, Springer, Heidelberg (1983)

   Google Scholar 

7. Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: FOCS, pp. 18–27 (1979)

   Google Scholar 

8. Chazelle, B., Guibas, L.J.: Fractional cascading: I. a data structuring technique. Algorithmica 1, 133–162 (1986)

   MATH  MathSciNet  Google Scholar 

9. Chazelle, B., Guibas, L.J.: Fractional cascading: Ii. applications. Algorithmica 1, 163–191 (1986)

   MATH  MathSciNet  Google Scholar 

10. Cole, R.: Searching and storing similar lists. J. Algorithms 7, 202–220 (1986)

    Article  MATH  MathSciNet  Google Scholar 

11. Sen, S.: Fractional cascading revisited. J. Algorithms 19, 161–172 (1995)

    Article  MATH  MathSciNet  Google Scholar 

12. Mehlhorn, K., Näher, S.: Dynamic fractional cascading. Algorithmica 5, 215–241 (1990)

    Article  MATH  MathSciNet  Google Scholar 

13. Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38, 86–124 (1989)

    Article  MATH  MathSciNet  Google Scholar 

14. Sarnak, N.: Persistend Data Structures. Ph.D thesis, New York University (1986)

    Google Scholar 

15. Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29, 669–679 (1986)

    Article  MathSciNet  Google Scholar 

16. Mulmuley, K.: Computational Geometry: An Introduction through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1993)

    MATH  Google Scholar 

17. Pugh, W.: Skip lists: A probabilistic alternative to balanced trees. Commun. ACM 33, 668–676 (1990)

    Article  Google Scholar 

18. Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16, 464–497 (1996)

    Article  MATH  MathSciNet  Google Scholar 

19. Eppstein, D., Goodrich, M.T., Sun, J.Z.: The skip quadtree: a simple dynamic data structure for multidimensional data. In: Symposium on Computational Geometry, pp. 296–305 (2005)

    Google Scholar 

20. Carter, J.L., Wegman, M.N.: Universal classes of hash functions. JCSS 18, 143–154 (1979)

    MATH  MathSciNet  Google Scholar 

21. Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31, 538–544 (1984)

    Article  MATH  Google Scholar 

22. Dietzfelbinger, M., Karlin, A.R., Mehlhorn, K., auf der Heide, F.M., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput. 23, 738–761 (1994)

    Article  MATH  MathSciNet  Google Scholar 

23. Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51, 122–144 (2004)

    Article  MATH  MathSciNet  Google Scholar 

24. Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533–551 (1994)

    Article  MATH  MathSciNet  Google Scholar 

25. van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 80–82 (1977)

    Article  MATH  Google Scholar 

26. Andersson, A.: Searchin dn priority queues in o(log n) time. In: Mehta, Sahni (eds.) Handbook of Data Structures and Applications, Chapman & Hall/CRC (2005)

    Google Scholar 

27. Mehlhorn, K., Näher, S.: Leda: A platform for combinatorial and geometric computing. Commun. ACM 38, 96–102 (1995)

    Article  Google Scholar 

Download references