Data structures and algorithms for disjoint set union problems | ACM Computing Surveys
- ️ItalianoGiuseppe F.
- ️Sun Sep 01 1991
References
[1]
ACK~RMAN, W. 1928. Zum Hilbertshen Aufbau der reelen Zahlen. Math. Ann. 99, 118-133.
[2]
ADELSON-VELSKn, G. M., AND LANDIS, Y. M. 1962. An algorithm for the organization of the information. Soviet. Math. Dokl. 3, 1259-1262.
[3]
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.
[4]
AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.
[5]
AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1983. Data Structures and Algorithms. Addison-Wesley, Reading, Mass.
[6]
AHUJA, R. K., MEHLHORN, K., ORLIN, J. B., AND TAR JAN, R. E. 1990. Faster algorithms for the shortest path problem. J. ACM 37, 213-223.
[7]
Ai'T-KAcI, H. 1986. An algebraic semantics approach to the effective resolution of type equations. Theor. Comut. Sci. 45, 293 351.
[8]
Ai'T-KAcI, H., AND NASR, R. 1986 LOGIN: A logic programming language with built-in inheritance. J. Logic Program. 3.
[9]
APOSTOLICO, A., AND GUERRA, C. 1987 The longest common subsequence problem revisited. Algor~thmica 2, 315-336.
[10]
APOSTOLICO, A., GAMBOSI, G., ITALIANO, G. F., AND TALAMO, M 1989. The set union problem with unlimited backtracking. Tech. Rep. CS-TR-908, Dept. of Computer Science, Purdue University.
[11]
ARDEN, B. W., GALLER, B. A., AND GRAHAM, R M 1961. An algorithm for equivalence declarations. Commun. ACM 4,310-314.
[12]
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.
[13]
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.
[14]
BEN-AMRAM, A. M., AND GALIL, Z. 1990. On a tradeoff in data structures. Manuscript.
[15]
BLUM, N. 1986. On the single operation worst-case time complexity of the disjoint set union problem. SIAM J. Comput. 15, 1021-1024
[16]
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.
[17]
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.
[18]
CLOCKSIN, W. F., AND MELLISH, C. S. 1981. Programming in Prolog. Springer-Verlag, Berhn.
[19]
DOYLE, J., AND RIVEST, R. 1976. Linear expected time of a simple union-find algorithm. Inf. Process. Lett. 5, 146-148.
[20]
DRISCOLL, J. R., SARNAK, N., SLEATOR, D. D., AND TAR JAN, R. E. 1989. Making data structures persistent. J Comput. Syst. Sci. 38, 86-124.
[21]
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.
[22]
ERD()S, P. AND R~NYI, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. bf5, 17-61.
[23]
EVEN, S. AND SmLOACH, Y. 1981. An on-line edge deletion problem. J. ACM28, 1-4.
[24]
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.
[25]
FREDMAN, M. L. 1989. On the cell probe complexity of the set union problem. Tech. Memorandum TM-ARH-013-570, Bell Communications Research.
[26]
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.
[27]
FREDMAN, M. L., AND TARJAN, R. E. 1987. F~- bonacci heaps and their uses in improved network optimization algorithms. J ACM 34, 596 615.
[28]
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
[29]
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.
[30]
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
[31]
GALIL, Z., ITALIANO, G. F. 1989. A note on set union with arbitrary deunions. Inf Process. Lett. 37, pp. 331 335.
[32]
GALLER, B. A., AND FISCHER, M. *J. 1954. An improved equivalence algorithm Commun. ACM 7, 301-303.
[33]
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.
[34]
GAMBOSI, G., ITALIANO, G. F., ANB TALAMO, M. 1989. Worst-case analysis of the act union problem with extended backtracking'. Theor. Comput. Sci. 68 (1989), 57-70.
[35]
GAMBOSI, G., ITALIANO, G F., AND TALAMO, M. 1991. The set union problem with dynamic weighted backtracking. BIT. To be published
[36]
HART, S., AND SHARIR, M. 1986. Non-linearity of Davenport Schinzel Sequences and of general ized path compression schemes. Combmatonca 6, 151-177.
[37]
HOGGER, C. J. 1984. Introduction to Logic Programming. Academic Press.
[38]
HOPCROFT, J. E., AND KARP, R M. 1971. An algorithm for testing the equivalence of finite automata. Tech. Rep. TR-71-114, Dept. of Computer Science, Cornell University, Ithaca, N.Y.
[39]
HOPCROFT, J. E., AND ULLMAN, J. D. 1973. Set merging algorithms. SIAM J. Comput. 2, 294-303.
[40]
HUDDLESTON, S., AND MEHLHORN, K. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 157-184.
[41]
HUET, G. 1976. Resolutions d'equations dens les langages d'ordre 1, 2,. ~o. Ph.D. dissertation, Univ. de Paris VII, France.
[42]
HUNT, J. W., AND SZYMANSKI, T. G. 1977. A fast algorithm for computing longest common subsequences. Commun. ACM 20, 350-353.
[43]
IBARAK1, T. 1978. M-depth search in branch and bound algorithms. Int. J. Comput. Inf. Sci. 7, 313-373.
[44]
IMAm, T., AND ASANO, T. 1987. Dynamic segment intersection with applications. J. Algorithms 8, 1-18.
[45]
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.
[46]
KARLSSON, R. G. 1984. Algorithms in a restricted universe. Tech. Rep. CS-84-50, Dept. of Computer Science, University of Waterloo.
[47]
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.
[48]
KMGHT, K. 1989. Unification: a multidisciplinary survey ACM Comput. Surv. 21, 93-124.
[49]
KNUT~, D. E. 1968. The Art of Computer Programming. Vol. 1, Fundamental Algorithms. Addison-Wesley, Reading, Mass.
[50]
KNUTH, D. E. 1976. Big omicron and big omega and big theta. SIGACT News 8, 18-24.
[51]
KNUTH, D. E., AND SCH6NAGE, A. 1978. The expected linearity of a simple equivalence algorithm. Theor. Comput. Sci. 6, 281-315.
[52]
KOLMOGORV, A. N. 1953. On the notion of algorithm. Uspehi Mat. Nauk. 8, 175-176.
[53]
KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Prec. Am. Math. Soc. 7, 48-50.
[54]
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.
[55]
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.
[56]
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.
[57]
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.
[58]
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.
[59]
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.
[60]
MANNmA, H., AND UKKONEN, E. 1987. Space-time optimal algorithms for the set union problem with backtracking. Tech. Rep. C-1987-80, Dept. of Computer Science, University of Helsinki, Helsinki, Finland.
[61]
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.
[62]
MEHLItORN, K. 1984a. Data Structures and Algorithms. Vol. 1, Sorting and Searching. Springer-Verlag, Berlin.
[63]
MEHLHORN, K. 1984b. Data Structures and Algorithms. Vol. 2, Graph Algorithms and NP- Completeness. Springer-Verlag, Berlin.
[64]
M~nL~ORN, K. 1984c. Data Structures and Algorithms. Vol. 3, Multzdimensional Searching and Computatwnal Geometry. Springer-Verlag, Berlin.
[65]
MEHLHORN, K., AND NJ(HER, S. 1990. Dynamic fractional cascading. Algorithmica 5, 215-241.
[66]
MEHLHORN, K., N,~HER, S., AND ALT, H. 1988. A lower bound for the complexity of the unionsplit-find problem. SlAM J. Comput. 17, 1093-1102.
[67]
NIEVERGELT, J., AND REINGOLD, E. M. 1973. Binary search trees of bounded balance. SlAM J'. Comput. 2, 33-43.
[68]
OVERMARS, M. H. 1983. The design of dynamic data structures, Lecture Notes in Computer Science 156. Springer-Verlag, Berlin.
[69]
PEARL, J. 1984. Heuristics. Addison-Wesley, Reading, Mass.
[70]
SCHONAGE, A. 1980. Storage modification machines. SIAM J. Comput. 9. 490-508.
[71]
STEARNS, R. E., AND LEWIS, P. M. 1969. Property grammars and table machines. Inf. Control 14, 524-549.
[72]
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.
[73]
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.
[74]
TARJAN, R. E. 1974. Finding dominators in directed graphs. SlAM J. Comput. 3, 62-89.
[75]
TAR JAN, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 215-225.
[76]
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.
[77]
TARJAN, R. E. 1979b. Application of path compression on balanced trees. J. ACM 26, 690-715.
[78]
TAR JAN, R. E. 1982. Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14, 30-33
[79]
TARJAN, R. E. 1983. Data structures and network algorithms. SIAM, Philadelphia, Penn.
[80]
TARJAN, R. E. 1985. Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6, 306-318.
[81]
TARJAN, R. E., AND VAN LE~UWEN, J. 1984. Worst-case analysis of set union algorithms. J. ACM 31,245-281.
[82]
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.
[83]
VAN EMDE BOAS, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 80-82
[84]
VAN EMDE BOAS, P., KAAS, R., AND ZIJLSTRA, E. 1977. Design and implementation of an efficient priority queue. Math. Syst Theory 10, 99-127.
[85]
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.
[86]
VITTER, J S., AND SIMONS, R. A. 1986. New classes for parallel complexity: A study of unification and other complete problems for P IEEE Trans. Comput. C-35.
[87]
WARREN, D. H D., AND PEREIRA, L. M. 1977. Prolog: The language and its implementation compared with LISP. ACM SIGPLAN Notices 12, 109-115.
[88]
WESTBROOK, J. 1989. Algorithms and data structures for dynamic graphs problems Ph.D. dis~ sertation. Also Tech. Rep. CS-TR-229-89, Dept. of Computer Science, Princeton University, Princeton, N.J
[89]
WESTBROOK, J., AND TAR JAN, R. E. 1989a. Amortized analysis of algorithms for set union with backtracking. SIAM J Comput. 18, 1-11.
[90]
WESTBROOK, J., AND TA~JAN, R. E. 1989b. Maintaining bridge-connected and biconnected components on-line. Tech. Rep. CS-TR-228-89, Dept. of Computer Science, Princeton University, Princeton, N.J.
[91]
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.
[92]
YAO, A. C. 1981. Should tables be sorted? J. ACM 28,615-628.
Information & Contributors
Information
Published In
ACM Computing Surveys Volume 23, Issue 3
Sept. 1991
136 pages
Copyright © 1991 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 September 1991
Published in CSUR Volume 23, Issue 3
Permissions
Request permissions for this article.
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- Downloads (Last 12 months)429
- Downloads (Last 6 weeks)64
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
- Yang LLi M(2024)Emergence of biconnected clusters in explosive percolationPhysical Review E10.1103/PhysRevE.110.014122110:1Online publication date: 16-Jul-2024
- Franke MStanojev OMitridati LHug G(2024)Privacy-preserving distributed market mechanism for active distribution networksElectric Power Systems Research10.1016/j.epsr.2024.110616234(110616)Online publication date: Sep-2024
- Liu TYe HZheng JZheng YChen J(2024)Advancing Front Mesh Generation on Dirty Composite SurfacesComputer-Aided Design10.1016/j.cad.2024.103683169:COnline publication date: 1-Apr-2024
- Peng PJi SÖzsu MZou L(2024)Minimum motif-cut: a workload-aware RDF graph partitioning strategyThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00860-133:5(1517-1542)Online publication date: 8-Jul-2024
- Chu ZSakai TAi QLiu Y(2023)Chuweb21D: A Deduped English Document Collection for Web Search TasksProceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval in the Asia Pacific Region10.1145/3624918.3625317(63-72)Online publication date: 26-Nov-2023
- Sahebolamri ABarrett LMoore SMicinski K(2023)Bring Your Own Data Structures to DatalogProceedings of the ACM on Programming Languages10.1145/36228407:OOPSLA2(1198-1223)Online publication date: 16-Oct-2023
- Li YWang JChen HJiang XLiu Y(2023)Object-Aware View Planning for Autonomous 3-D Model Reconstruction of Buildings Using a Mobile RobotIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2023.327942472(1-15)Online publication date: 2023
- Choe CAhn SDoh NNam C(2023)Reduction of LiDAR Point Cloud Maps for Localization of Resource-Constrained Robotic SystemsIEEE Systems Journal10.1109/JSYST.2022.316292617:1(916-927)Online publication date: Mar-2023
- Huang JTan YLee DDesaraju VGrizzle J(2023) Informable Multi-Objective and Multi-Directional RRT * System for Robot Path Planning 2023 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48891.2023.10160838(5666-5673)Online publication date: 29-May-2023
- Dutta AHarshith JSoni YGupta AGupta VGupta A(2023)Computational Time Complexity for Sorting Algorithm amalgamated with Quantum Search2023 International Conference for Advancement in Technology (ICONAT)10.1109/ICONAT57137.2023.10080217(1-6)Online publication date: 24-Jan-2023
- Show More Cited By
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.