Worst-case and amortised optimality in union-find (extended abstract). (English) Zbl 1346.68247
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 499-506 (1999).
MSC:
| 68W05 | Nonnumerical algorithms |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | S. Alstrup, T. Husfeldt, and T. Rauhe. Marked ancestor problems. In Proc. 39th Syrup. Found. of Comp. Sci. (FOGS), pages 534-543, t998. |
| [2] | L. Banachowski. A complement to Tarjan’s result about the lower bound on the complexity of the set union problem. Information Processing Letters, 11:59-65, 1980. · Zbl 0453.68039 |
| [3] | A. M. Ben-Amram. On the power of random access machines. PhD thesis, 1995. · Zbl 1412.68057 |
| [4] | A. M. Ben-Amram. What is a “pointer machine”? \(IGACT News, 26(2):88-95, 1995. See also http://www.diku.dk/researchgro ups / t opps/b i b 1 i ogr aphy/1998, html #D- 351. 10.1145/202840.20284\) |
| [5] | A. M. Ben-Amram and Z. Galil. A generalization of a lower-bound technique due to Predman and Saks. submitted for publication 1998. · Zbl 0992.68034 |
| [6] | N. Blum. On the single operation worst-case time complexity of the disjoint set union problem. SIAM J. Comput., 15:1021-1024, 1986. 10.1137/0215072 · Zbl 0619.68039 |
| [7] | M. L. Fredman. On the ceil probe complexity of the set union problem. Technical Report TM-ARH-013-570, Bell Comunications Research, 1989. |
| [8] | M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures. In Proc. 1st Syrup. Theory of Computing (STOC), pages 345-354, 1989. 10.1145/73007.73040 |
| [9] | H. N. G bow. A scaling algorithm for weighted matching on general graphs. In Proc. 6th Syrup. Found. of Comp. \(ci. (FOCS), pages 90-100, 1985\) |
| [10] | H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st Syrup. on Discrete Alg. (SODA), pages 434-443, 1990. · Zbl 0800.68617 |
| [11] | Z. Galil and G. F. Italiano. Data structures and algorithms for disjoin set union problems. A CM Comp. Surveys, 23(3):319, 1991. 10.1145/116873.116878 |
| [12] | J. La Poutr6. Lower bounds for the unionfind and the split-find problem on pointer ma. chines. Journal of Computer and Systems Sciences, 52(I):87-99, 1996. See also STOC’90. 10.1006/jcss.1996.0008 · Zbl 0846.68035 |
| [13] | J. A. La Poutr . New techniques for the unionfind problem. In D. Johnson, editor, Proc. 1st Syrup. on Discrete Alg. (SODA), pages 54-63, 1990. · Zbl 0800.68450 |
| [14] | K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer- Verlag, 1984. · Zbl 0556.68001 |
| [15] | M. Smid. A data structure for the unionfind problem having good single-operation complexity. ALCOM: Algorithms Review, Newsletter of the ESPRIT H Basic Research Actions Program Project no. 3075 (ALCOM), 1, 1990. |
| [16] | R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the A CM, 22:215-225, 1975. 10.1145/321879.321884 · Zbl 0307.68029 |
| [17] | R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and Systems Sciences, 18(2):110-127, 1979. · Zbl 0413.68039 |
| [18] | R. E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245-281, 1984. 10.1145/62.2160 · Zbl 0632.68043 |
| [19] | A. C. Yao. Should tables be sorted? Journal of the A CM, 28(3):615-628, 1981. 10.1145/322261.322274 · Zbl 0462.68079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
