Lower bounds for dynamic connectivity. (English) Zbl 1192.68185
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 546-553, electronic only (2004).
References:
| [1] | P. Beame and F. E. Fich. Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences, 65(1):38-72, 2002.]] 10.1006/jcss.2002.1822 · Zbl 1020.68027 |
| [2] | P. F. Dietz. Optimal algorithms for list indexing and subset rank. In Proc. 1st Workshop on Algorithms and Data Structures (WADS), pages 39-46, 1989.]] · Zbl 0766.68057 |
| [3] | D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. R. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic planar graph. Journal of Computer and System Sciences, 13(1):33-54, 1992.]] 10.1016/0196-6774(92)90004-V · Zbl 0751.05081 |
| [4] | P. M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3):327-336, 1994.]] 10.1002/spe.4380240306 |
| [5] | M. L. Fredman. The complexity of maintaining an array and computing its partial sums. Journal of the ACM, 29(1):250-260, 1982.]] 10.1145/322290.322305 · Zbl 0477.68046 |
| [6] | M. L. Fredman and M. R. Henzinger. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica, 22(3):351-362, 1998.]] · Zbl 0915.68132 |
| [7] | M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM Symposium on Theory of Computing (STOC), pages 345-354, 1989.]] 10.1145/73007.73040 |
| [8] | H. Hampapuram and M. L. Fredman. Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM Journal on Computing, 28(1):1-9, 1998.]] 10.1137/S0097539795291598 · Zbl 0914.68041 |
| [9] | M. R. Henzinger and V. King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502-516, 1999.]] 10.1145/320211.320215 · Zbl 1065.68665 |
| [10] | J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723-760, 2001.]] 10.1145/502090.502095 · Zbl 1127.68408 |
| [11] | W. -K. Hon, K. Sadakane, and W. -K. Sung. Succinct data structures for searchable partial sums. In Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC), pages 505-516, 2003.]] · Zbl 1205.68129 |
| [12] | T. Husfeldt and T. Rauhe. New lower bound techniques for dynamic partial sums and related problems. SIAM Journal on Computing, 32(3):736-753, 2003.]] 10.1137/S0097539701391592 · Zbl 1046.68055 |
| [13] | P. B. Miltersen. Cell probe complexity - a survey. In Advances in Data Structures Workshop, Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999.]] |
| [14] | P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130(1):203-236, 1994.]] 10.1016/0304-3975(94)90159-7 · Zbl 0808.68061 |
| [15] | M. Pǎtra7#351;cu and E. D. Demaine. Tight bounds for the partial-sums problem. In Proc. 15th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 20-29, 2004.]] · Zbl 1317.68080 |
| [16] | R. Raman, V. Raman, and S. S. Rao. Succinct dynamic data structures. In Proc. 7th Workshop on Algorithms and Data Structures (WADS), pages 426-437, 2001.]] · Zbl 0997.68520 |
| [17] | D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983.]] 10.1016/0022-0000(83)90006-5 · Zbl 0509.68058 |
| [18] | M. Thorup. Near-optimal fully-dynamic graph connectivity. In Proc. 32nd ACM Symposium on Theory of Computing (STOC), pages 343-350, 2000.]] 10.1145/335305.335345 · Zbl 1296.05110 |
| [19] | A. C. -C. Yao. Should tables be sorted? Journal of the ACM, 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.
