{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T08:31:00Z","timestamp":1768033860006,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642131929","type":"print"},{"value":"9783642131936","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13193-6_35","type":"book-chapter","created":{"date-parts":[[2010,4,27]],"date-time":"2010-04-27T11:54:59Z","timestamp":1272369299000},"page":"411-423","source":"Crossref","is-referenced-by-count":34,"title":["Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure"],"prefix":"10.1007","author":[{"given":"Md. Mostofa Ali","family":"Patwary","sequence":"first","affiliation":[]},{"given":"Jean","family":"Blair","sequence":"additional","affiliation":[]},{"given":"Fredrik","family":"Manne","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","unstructured":"Bader, D.A., Madduri, K.: GTGraph: A synthetic graph generator suite (2006), http:\/\/www.cc.gatech.edu\/~kamesh\/GTgraph"},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(80)90001-0","volume":"11","author":"L. Banachowski","year":"1980","unstructured":"Banachowski, L.: A complement to Tarjan\u2019s result about the lower bound on the complexity of the set union problem. Inf. Proc. Letters\u00a011, 59\u201365 (1980)","journal-title":"Inf. Proc. Letters"},{"key":"35_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"35_CR4","unstructured":"Davis, T.A.: University of Florida sparse matrix collection. Submitted to ACM Transactions on Mathematical Software"},{"key":"35_CR5","unstructured":"Dawes, B., Abrahams, D.: The Boost C++ libraries (2009), www.boost.org"},{"key":"35_CR6","volume-title":"A Discipline of Programming","author":"E.W. Dijkstra","year":"1976","unstructured":"Dijkstra, E.W.: A Discipline of Programming. Prentice-Hall, Englewood Cliffs (1976)"},{"issue":"3","key":"35_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/116873.116878","volume":"23","author":"Z. Galil","year":"1991","unstructured":"Galil, Z., Italiano, G.F.: Data structures and algorithms for disjoint set union problems. ACM Comput. Surv.\u00a023(3), 319\u2013344 (1991)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"35_CR8","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/S0895479892236921","volume":"15","author":"J.R. Gilbert","year":"1994","unstructured":"Gilbert, J.R., Ng, E.G., Peyton, B.W.: An efficient algorithm to compute row and column counts for sparse Cholesky factorization. SIAM J. Matrix Anal. Appl.\u00a015(4), 1075\u20131091 (1994)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"35_CR9","unstructured":"Hynes, R.: A new class of set union algorithms. Master\u2019s thesis, Department of Computer Science, University of Toronto, Canada (1998)"},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0611010","volume":"11","author":"J.W.H. Liu","year":"1990","unstructured":"Liu, J.W.H.: The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl.\u00a011, 134\u2013172 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Manne, F., Patwary, M.M.A.: A scalable parallel union-find algorithm for distributed memory computers. To appear in proc.\u00a0PPAM 2009. LNCS. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-14390-8_20"},{"key":"35_CR12","volume-title":"LEDA, A Platform for Combinatorial Geometric Computing","author":"K. Melhorn","year":"1999","unstructured":"Melhorn, K., N\u00e4her, S.: LEDA, A Platform for Combinatorial Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Osipov, V., Sanders, P., Singler, J.: The filter-Kruskal minimum spanning tree algorithm. In: ALENEX, pp. 52\u201361 (2009)","DOI":"10.1137\/1.9781611972894.5"},{"key":"35_CR14","unstructured":"Patwary, M.M.A., Blair, J., Manne, F.: Efficient Union-Find implementations. Tech. Report 393, Dept.\u00a0Computer Science, University of Bergen (2010), http:\/\/www.uib.no\/ii\/forskning\/reports-in-informatics\/reports-in-informatics-2010-2019"},{"key":"35_CR15","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jcss.1996.0008","volume":"52","author":"J.A.L. Poutr\u00e9","year":"1996","unstructured":"Poutr\u00e9, J.A.L.: Lower bounds for the union-find and the split-find problem on pointer machines. J. Comput. Syst. Sci.\u00a052, 87\u201399 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"35_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM\u00a022, 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"35_CR17","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci.\u00a018, 110\u2013127 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"35_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM\u00a031, 245\u2013281 (1984)","journal-title":"J. ACM"},{"key":"35_CR19","unstructured":"Wassenberg, J., Bulatov, D., Middelmann, W., Sanders, P.: Determination of maximally stable extremal regions in large images. In: Proc.\u00a0of Signal Processing, Pattern Recognition, and Applications (SPPRA). Acta Press (2008)"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10044-008-0109-y","volume":"12","author":"K. Wu","year":"2009","unstructured":"Wu, K., Otoo, E., Suzuki, K.: Optimizing two-pass connected-component labeling algorithms. Pattern Anal. Appl.\u00a012, 117\u2013135 (2009)","journal-title":"Pattern Anal. Appl."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13193-6_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:02:38Z","timestamp":1606186958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13193-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131929","9783642131936"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13193-6_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}