{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T20:25:48Z","timestamp":1724703948076},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"name":"NKFI","award":["108448"],"award-info":[{"award-number":["108448"]}]},{"name":"New National Excellence Program of the Ministry of Human Capacities","award":["UNKP-17-3"],"award-info":[{"award-number":["UNKP-17-3"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> Disjoint-Set forests, consisting of Union-Find trees, are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact structural characterization of these trees is known (such a characterization exists for Union trees which are constructed without using path compression) for the case assuming union-by-rank strategy for merging. In this paper we provide such a characterization by means of a simple PUSH operation and show that the decision problems whether a (ranked or unranked) tree is a Union-Find tree are NP-complete, complementing our earlier similar result for the union-by-size strategy. <\/jats:p>","DOI":"10.1142\/s0129054119400276","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1029-1045","source":"Crossref","is-referenced-by-count":2,"title":["Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info"],"prefix":"10.1142","volume":"30","author":[{"given":"Kitti","family":"Gelle","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Szeged, Hungary"}]},{"given":"Szabolcs","family":"Iv\u00e1n","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Szeged, Hungary"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400276BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45138-9_15"},{"key":"S0129054119400276BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90037-A"},{"key":"S0129054119400276BIB003","series-title":"LIPIcs","first-page":"289","volume-title":"26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009","volume":"3","author":"Cl\u00e9ment J.","year":"2009"},{"key":"S0129054119400276BIB004","series-title":"McGraw-Hill Higher Education","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","edition":"2"},{"key":"S0129054119400276BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13509-5_23"},{"key":"S0129054119400276BIB006","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2008030"},{"key":"S0129054119400276BIB007","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2002012"},{"issue":"1","key":"S0129054119400276BIB008","first-page":"51","volume":"10","author":"Duval J.-P.","year":"2005","journal-title":"Journal of Automata, Languages, and Combinatorics"},{"key":"S0129054119400276BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"key":"S0129054119400276BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/364099.364331"},{"key":"S0129054119400276BIB011","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0129054119400276BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9522-8"},{"key":"S0129054119400276BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.11.003"},{"key":"S0129054119400276BIB014","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/978-3-642-00982-2_36","volume-title":"Language and Automata Theory and Applications","volume":"5457","author":"Tomohiro I.","year":"2009"},{"key":"S0129054119400276BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.008"},{"key":"S0129054119400276BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/62029.62030"},{"key":"S0129054119400276BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.009"},{"key":"S0129054119400276BIB019","first-page":"223","volume":"42","author":"Lu W.","year":"2000","journal-title":"The Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"S0129054119400276BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.09.009"},{"key":"S0129054119400276BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.01.005"},{"key":"S0129054119400276BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"S0129054119400276BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36383-1_11"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T00:29:44Z","timestamp":1590107384000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":22,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400276"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400276","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}