Data structures and algorithms for disjoint set union problems
Tóm tắt
Từ khóa
Tài liệu tham khảo
ACK~RMAN , W. 1928 . Zum Hilbertshen Aufbau der reelen Zahlen . Math. Ann. 99 , 118 - 133 . ACK~RMAN, W. 1928. Zum Hilbertshen Aufbau der reelen Zahlen. Math. Ann. 99, 118-133.
ADELSON-VELSK n, G. M., AND LANDIS , Y. M. 1962 . An algorithm for the organization of the information . Soviet. Math. Dokl. 3 , 1259 - 1262 . ADELSON-VELSKn, G. M., AND LANDIS, Y. M. 1962. An algorithm for the organization of the information. Soviet. Math. Dokl. 3, 1259-1262.
AH o, A. V., HOPCROFT , J. E. , AND ULLMAN , J. D. 1973 . On computing least common ancestors in trees . In Proceedings of the 5th Annual ACM Symposium on Theory of Computing. ACM Press , New York, NY , pp. 253 - 265 . 10.1145/800125.804056 AHo, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1973. On computing least common ancestors in trees. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp. 253-265. 10.1145/800125.804056
AHO , A. V. , HOPCROFT , J. E. , AND ULLMAN , J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley , Reading, Mass . AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.
AHO , A. V. , HOPCROFT , J. E. , AND ULLMAN , J. D. 1983. Data Structures and Algorithms . Addison-Wesley , Reading, Mass . AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1983. Data Structures and Algorithms. Addison-Wesley, Reading, Mass.
Ai 'T-KA c I, H . 1986 . An algebraic semantics approach to the effective resolution of type equations . Theor. Comut. Sci. 45 , 293 351. Ai'T-KAcI, H. 1986. An algebraic semantics approach to the effective resolution of type equations. Theor. Comut. Sci. 45, 293 351.
Ai'T-KAcI H. AND NASR R. 1986 LOGIN: A logic programming language with built-in inheritance. J. Logic Program. 3. 10.1016/0743-1066(86)90013-0 Ai'T-KAcI H. AND NASR R. 1986 LOGIN: A logic programming language with built-in inheritance. J. Logic Program. 3. 10.1016/0743-1066(86)90013-0
APOSTOLICO , A. , AND GUERRA , C. 1987 The longest common subsequence problem revisited . Algor~thmica 2 , 315 - 336 . APOSTOLICO, A., AND GUERRA, C. 1987 The longest common subsequence problem revisited. Algor~thmica 2, 315-336.
BANACHOWSKI , L. 1980 . A complement of Tarjan's result about the lower bound on the complexity of the set union problem . Inf. Process. Lett. 11 , 59 65. BANACHOWSKI, L. 1980. A complement of Tarjan's result about the lower bound on the complexity of the set union problem. Inf. Process. Lett. 11, 59 65.
BEN-AMRAM , A. M. , AND GAL m, Z. 1988 . On pointers versus addresses . In Proceedings of the 29th Annual Symposzum on Foundations of Computer Science. IEEE Computer Society , pp 532 - 538 . To appear in J. ACM. 10.1145/146637.146666 BEN-AMRAM, A. M., AND GALm, Z. 1988. On pointers versus addresses. In Proceedings of the 29th Annual Symposzum on Foundations of Computer Science. IEEE Computer Society, pp 532-538. To appear in J. ACM. 10.1145/146637.146666
BEN-AMRAM A. M. AND GALIL Z. 1990. On a tradeoff in data structures. Manuscript. BEN-AMRAM A. M. AND GALIL Z. 1990. On a tradeoff in data structures. Manuscript.
BOLLOBAS , B. , AND SIMON , I. 1985 . On the expected behaviour of disjoint set union problems . In Proceedings of the 17th Annual ACM Symposium on Theory of Computing ACM Press , New York, NY , pp. 224 - 231 . 10.1145/22145.22171 BOLLOBAS, B., AND SIMON, I. 1985. On the expected behaviour of disjoint set union problems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing ACM Press, New York, NY, pp. 224-231. 10.1145/22145.22171
BROWN , M. R. , AND TARJAN , R. E 1980 . Design and analysis of a data structure for representing sorted lists . SlAM J. Comput. 9 , 594 614. BROWN, M. R., AND TARJAN, R. E 1980. Design and analysis of a data structure for representing sorted lists. SlAM J. Comput. 9, 594 614.
CLOCKSIN , W. F. , AND MELLISH , C. S. 1981. Programming in Prolog . Springer-Verlag , Berhn . CLOCKSIN, W. F., AND MELLISH, C. S. 1981. Programming in Prolog. Springer-Verlag, Berhn.
DOYLE , J. , AND RIVEST , R. 1976 . Linear expected time of a simple union-find algorithm . Inf. Process. Lett. 5 , 146 - 148 . DOYLE, J., AND RIVEST, R. 1976. Linear expected time of a simple union-find algorithm. Inf. Process. Lett. 5, 146-148.
EPPSTEIN , D. , GALIL , Z. , GIANCARLO , R. AND ITALIANO , G F . 1990 . Sparse dynamic programming . In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Applied and Industrial Mathematics , Philadelphia, PA , pp. 513 - 522 . To appear in J. ACM. EPPSTEIN, D., GALIL, Z., GIANCARLO, R. AND ITALIANO, G F. 1990. Sparse dynamic programming. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Applied and Industrial Mathematics, Philadelphia, PA, pp. 513-522. To appear in J. ACM.
ERD () S, P . AND R~NYI , A. 1960 . On the evolution of random graphs . Publ. Math. Inst. Hungar. Acad. Sci. bf5 , 17 - 61 . ERD()S, P. AND R~NYI, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. bf5, 17-61.
EVEN S. AND SmLOACH Y. 1981. An on-line edge deletion problem. J. ACM28 1-4. 10.1145/322234.322235 EVEN S. AND SmLOACH Y. 1981. An on-line edge deletion problem. J. ACM28 1-4. 10.1145/322234.322235
FISCHER , M. J. 1972. Efficiency of equivalence algorithms . In Complexity of Computer Computations , R. E. Miller and J. W. Thatcher, Eds. Plenum Press , New York , pp. 153 - 168 . FISCHER, M. J. 1972. Efficiency of equivalence algorithms. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, pp. 153-168.
FREDMAN M. L. 1989. On the cell probe complexity of the set union problem. Tech. Memorandum TM-ARH-013-570 Bell Communications Research. FREDMAN M. L. 1989. On the cell probe complexity of the set union problem. Tech. Memorandum TM-ARH-013-570 Bell Communications Research.
FREDMAN , M. L. AND SAKS , M. E. 1989 . The cell probe complexity of dynamic data structures . In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. ACM Press , New York, NY , pp. 345 - 354 . 10.1145/73007.73040 FREDMAN, M. L. AND SAKS, M. E. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp. 345-354. 10.1145/73007.73040
GABOW , H. N. 1985 . A scaling algorithm for weighted matching on general graphs In Proceedings of the 26th Annual Symposium on Foundations of Computer Sczence . IEEE Computer Society , pp. 90 - 100 GABOW, H. N. 1985. A scaling algorithm for weighted matching on general graphs In Proceedings of the 26th Annual Symposium on Foundations of Computer Sczence. IEEE Computer Society, pp. 90-100
GABOW , H. N. , AND TAR JAN , R. E. 1985 . A linear time algorithm for a special case of disjoint set union . J. Comput. Syst. Sci. 30 , 209 - 221 . GABOW, H. N., AND TAR JAN, R. E. 1985. A linear time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209-221.
GAIBISSO , C. , GAMBOSI , G. , AND TALAMO , M. 1987 A partially persistent data structure for the set union problem . RAIRO Theoretical Informatics and Applicatmns. 24 , pp. 189 - 202 GAIBISSO, C., GAMBOSI, G., AND TALAMO, M. 1987 A partially persistent data structure for the set union problem. RAIRO Theoretical Informatics and Applicatmns. 24, pp. 189-202
GAMBOSI , G. , ITALIANO , G. F. , AND TALAMO , M. 1988 . Getting back to the past in the union find problem . In Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS 1988). Lecture Notes in Computer Science 294. Sprmger-Verlag, Berlin , pp. 8 - 17 . GAMBOSI, G., ITALIANO, G. F., AND TALAMO, M. 1988. Getting back to the past in the union find problem. In Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS 1988). Lecture Notes in Computer Science 294. Sprmger-Verlag, Berlin, pp. 8-17.
GAMBOSI G. ITALIANO G F. AND TALAMO M. 1991. The set union problem with dynamic weighted backtracking. BIT. To be published GAMBOSI G. ITALIANO G F. AND TALAMO M. 1991. The set union problem with dynamic weighted backtracking. BIT. To be published
HOGGER , C. J. 1984. Introduction to Logic Programming . Academic Press . HOGGER, C. J. 1984. Introduction to Logic Programming. Academic Press.
HOPCROFT , J. E. , AND ULLMAN , J. D. 1973 . Set merging algorithms . SIAM J. Comput. 2 , 294 - 303 . HOPCROFT, J. E., AND ULLMAN, J. D. 1973. Set merging algorithms. SIAM J. Comput. 2, 294-303.
HUDDLESTON , S. , AND MEHLHORN , K. 1982 . A new data structure for representing sorted lists . Acta Inf. 17 , 157 - 184 . HUDDLESTON, S., AND MEHLHORN, K. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 157-184.
IBARAK 1, T. 1978 . M-depth search in branch and bound algorithms . Int. J. Comput. Inf. Sci. 7 , 313 - 373 . IBARAK1, T. 1978. M-depth search in branch and bound algorithms. Int. J. Comput. Inf. Sci. 7, 313-373.
ITALIANO , G. F. , AND SARNAK , N. 1991 . Fully persistent data structures for disjoint set union problems . In Proceedings Workshop on Algorithms and Data Structure ( Ottawa, Canada). To appear. ITALIANO, G. F., AND SARNAK, N. 1991. Fully persistent data structures for disjoint set union problems. In Proceedings Workshop on Algorithms and Data Structure (Ottawa, Canada). To appear.
KERSCHENBAUM , A. , AND VAN SLYKE , R. 1972 . Computing minimum spanning trees efficiently . In Proceedings of the 25th Annual Conference of the ACM. ACM Press , New York, NY , pp. 518 - 527 . 10.1145/800193.569966 KERSCHENBAUM, A., AND VAN SLYKE, R. 1972. Computing minimum spanning trees efficiently. In Proceedings of the 25th Annual Conference of the ACM. ACM Press, New York, NY, pp. 518-527. 10.1145/800193.569966
KNUT~ , D. E. 1968. The Art of Computer Programming . Vol. 1 , Fundamental Algorithms. Addison-Wesley , Reading, Mass. KNUT~, D. E. 1968. The Art of Computer Programming. Vol. 1, Fundamental Algorithms. Addison-Wesley, Reading, Mass.
KNUTH , D. E. , AND SCH 6 NAGE , A. 1978 . The expected linearity of a simple equivalence algorithm . Theor. Comput. Sci. 6 , 281 - 315 . KNUTH, D. E., AND SCH6NAGE, A. 1978. The expected linearity of a simple equivalence algorithm. Theor. Comput. Sci. 6, 281-315.
KOLMOGORV , A. N. 1953 . On the notion of algorithm . Uspehi Mat. Nauk. 8 , 175 - 176 . KOLMOGORV, A. N. 1953. On the notion of algorithm. Uspehi Mat. Nauk. 8, 175-176.
KRUSKAL , J. B. 1956 . On the shortest spanning subtree of a graph and the traveling salesman problem . Prec. Am. Math. Soc. 7 , 48 - 50 . KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Prec. Am. Math. Soc. 7, 48-50.
LA POUTR~ , J. A. 1990 a. New techniques for the union-find problem . In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA , pp. 54 - 63 . LA POUTR~, J. A. 1990a. New techniques for the union-find problem. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 54-63.
LA POUTR~ , J. A. 1990 b. Lower bounds for the union-find and the split-find problem on pointer machines . In Proceedings of the 22th Annual ACM Symposium on Theory of Computing. ACM Press , New York, NY , pp. 34 - 44 . 10.1145/100216.100221 LA POUTR~, J. A. 1990b. Lower bounds for the union-find and the split-find problem on pointer machines. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp. 34-44. 10.1145/100216.100221
OEBL , M. , AND NE~ET fi IL, J . 1988 . Linearity and unprovability of set union problem strategies . In Proceedings of the 20th Annual ACM Symposium on Theory of Computing. ACM Press , New York, NY , pp. 360 - 366 . 10.1145/62212.62247 OEBL, M., AND NE~ETfiIL, J. 1988. Linearity and unprovability of set union problem strategies. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp. 360-366. 10.1145/62212.62247
MANN m A, H ., AN n UKK ONEN , E. 1986a. The set union problem with backtracking . In Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP 86) . Lecture Notes in Computer Science 226 . Springer-Verlag , Berlin , pp. 236 - 243 . MANNmA, H., ANn UKKONEN, E. 1986a. The set union problem with backtracking. In Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP 86). Lecture Notes in Computer Science 226. Springer-Verlag, Berlin, pp. 236-243.
MANNILA , H. , AND UKKONEN , E. 1986b. On the complexity of unification sequences . In Proceedmgs of the 3rd International Conference on Logic Programming . Lecture Notes in Computer Science 225 . Springer-Verlag , Berlin , pp. 122 - 133 . MANNILA, H., AND UKKONEN, E. 1986b. On the complexity of unification sequences. In Proceedmgs of the 3rd International Conference on Logic Programming. Lecture Notes in Computer Science 225. Springer-Verlag, Berlin, pp. 122-133.
MANNILA , H. , AND UKKONEN , E. 1986 c. Timestamped term representation for implementing Prolog . In Proceedings of the 3rd IEEE Conference on Logic Programming. The MIT Press , Cambridge, MA , pp. 159 - 167 . MANNILA, H., AND UKKONEN, E. 1986c. Timestamped term representation for implementing Prolog. In Proceedings of the 3rd IEEE Conference on Logic Programming. The MIT Press, Cambridge, MA, pp. 159-167.
MANNILA , H. , AND UKKONEN , E. 1988 . Time parameter and arbitrary deunions in the set union problem . In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT 88) . Lecture Notes in Computer Science 318. Springer-Verlag, Berlin , pp. 34 - 42 . MANNILA, H., AND UKKONEN, E. 1988. Time parameter and arbitrary deunions in the set union problem. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT 88). Lecture Notes in Computer Science 318. Springer-Verlag, Berlin, pp. 34-42.
MEHLI t ORN , K. 1984a. Data Structures and Algorithms . Vol. 1 , Sorting and Searching. Springer-Verlag , Berlin. MEHLItORN, K. 1984a. Data Structures and Algorithms. Vol. 1, Sorting and Searching. Springer-Verlag, Berlin.
MEHLHORN , K. 1984b. Data Structures and Algorithms . Vol. 2 , Graph Algorithms and NP- Completeness. Springer-Verlag , Berlin. MEHLHORN, K. 1984b. Data Structures and Algorithms. Vol. 2, Graph Algorithms and NP- Completeness. Springer-Verlag, Berlin.
M~ nL~ ORN , K. 1984c. Data Structures and Algorithms . Vol. 3 , Multzdimensional Searching and Computatwnal Geometry. Springer-Verlag , Berlin. M~nL~ORN, K. 1984c. Data Structures and Algorithms. Vol. 3, Multzdimensional Searching and Computatwnal Geometry. Springer-Verlag, Berlin.
MEHLHORN , K. , AND NJ ( HER , S. 1990 . Dynamic fractional cascading . Algorithmica 5 , 215 - 241 . MEHLHORN, K., AND NJ(HER, S. 1990. Dynamic fractional cascading. Algorithmica 5, 215-241.
NIEVERGELT , J. , AND REINGOLD , E. M. 1973 . Binary search trees of bounded balance . SlAM J'. Comput. 2 , 33 - 43 . NIEVERGELT, J., AND REINGOLD, E. M. 1973. Binary search trees of bounded balance. SlAM J'. Comput. 2, 33-43.
OVERMARS , M. H. 1983. The design of dynamic data structures , Lecture Notes in Computer Science 156 . Springer-Verlag , Berlin . OVERMARS, M. H. 1983. The design of dynamic data structures, Lecture Notes in Computer Science 156. Springer-Verlag, Berlin.
PEARL J. 1984. Heuristics. Addison-Wesley Reading Mass. PEARL J. 1984. Heuristics. Addison-Wesley Reading Mass.
SCHONAGE , A. 1980 . Storage modification machines . SIAM J. Comput. 9. 490 - 508 . SCHONAGE, A. 1980. Storage modification machines. SIAM J. Comput. 9. 490-508.
STEARNS , R. E. , AND LEWIS , P. M. 1969 . Property grammars and table machines . Inf. Control 14 , 524 - 549 . STEARNS, R. E., AND LEWIS, P. M. 1969. Property grammars and table machines. Inf. Control 14, 524-549.
STEARNS , R. E. , AND ROSENKRANTZ , P. M. 1969 . Table machine simulation . Conference Records IEEE lOth Annual Symposium on Switching and Automata Theory. IEEE Computer Society , pp. 118 - 128 . STEARNS, R. E., AND ROSENKRANTZ, P. M. 1969. Table machine simulation. Conference Records IEEE lOth Annual Symposium on Switching and Automata Theory. IEEE Computer Society, pp. 118-128.
TAR JAN , R. E. 1973 . Testing flow graph reproducibility In Proceedings of the 5th Annual ACM Symposium on Theory of Computing . ACM Press , New York, NY , pp. 96 - 107 . 10.1145/800125.804040 TAR JAN, R. E. 1973. Testing flow graph reproducibility In Proceedings of the 5th Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp. 96-107. 10.1145/800125.804040
TARJAN , R. E. 1974 . Finding dominators in directed graphs . SlAM J. Comput. 3 , 62 - 89 . TARJAN, R. E. 1974. Finding dominators in directed graphs. SlAM J. Comput. 3, 62-89.
TAR JAN , R. E. 1979 a. A class of algorithms which require non linear time to maintain disjoint sets . J. Comput. Syst. Sci. 18 , 110 - 127 . TAR JAN, R. E. 1979a. A class of algorithms which require non linear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 110-127.
TAR JAN , R. E. 1982 . Sensitivity analysis of minimum spanning trees and shortest path trees . Inf. Process. Lett. 14 , 30 - 33 TAR JAN, R. E. 1982. Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14, 30-33
TARJAN , R. E. 1983. Data structures and network algorithms . SIAM , Philadelphia, Penn . TARJAN, R. E. 1983. Data structures and network algorithms. SIAM, Philadelphia, Penn.
TARJAN , R. E. 1985 . Amortized computational complexity . SIAM J. Algebraic Discrete Methods 6 , 306 - 318 . TARJAN, R. E. 1985. Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6, 306-318.
VAN DER WE m E, T . 1980 . Data Structures: An Axiomatic Approach and the Use of Binomial Trees in Developing and Analyzing Algorithms. Mathematisch Centrum. Amsterdam, The Netherlands . VAN DER WEmE, T. 1980. Data Structures: An Axiomatic Approach and the Use of Binomial Trees in Developing and Analyzing Algorithms. Mathematisch Centrum. Amsterdam, The Netherlands.
VAN EMDE BOAS , P. 1977 . Preserving order in a forest in less than logarithmic time and linear space . Inf. Process. Lett. 6 , 80 - 82 VAN EMDE BOAS, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 80-82
VAN EMDE BOAS , P. , KAAS , R. , AND ZIJLSTRA , E. 1977 . Design and implementation of an efficient priority queue . Math. Syst Theory 10 , 99 - 127 . VAN EMDE BOAS, P., KAAS, R., AND ZIJLSTRA, E. 1977. Design and implementation of an efficient priority queue. Math. Syst Theory 10, 99-127.
VAN LEEUWEN , J. , AND VAN DER WEIDE , T. 1977 . Alternative path compression techmques. Tech. Rep. RUU-CS-77-3, Dept. of Computer Science, University of Utrecht , Utrecht, The Netherlands. VAN LEEUWEN, J., AND VAN DER WEIDE, T. 1977. Alternative path compression techmques. Tech. Rep. RUU-CS-77-3, Dept. of Computer Science, University of Utrecht, Utrecht, The Netherlands.
YAO , A C . 1976 . On the average behavior of set merging algorithms . In Proceedings of the 8th Annual ACM Symposium on Theory of Computing. ACM Press , New York, NY , pp 192 - 195 . 10.1145/800113.803648 YAO, A C. 1976. On the average behavior of set merging algorithms. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing. ACM Press, New York, NY, pp 192-195. 10.1145/800113.803648