{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T13:33:45Z","timestamp":1791898425934,"version":"4.3.4"},"reference-count":9,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>We consider the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An $O(n)$ expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.<\/jats:p>","DOI":"10.1137\/0214010","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"129-133","source":"Crossref","is-referenced-by-count":10,"title":["On the Expected Performance of Path Compression Algorithms"],"prefix":"10.1137","volume":"14","author":[{"given":"Andrew C.","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90061-2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_14"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/364099.364331"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90009-9"},{"key":"R6","unstructured":"M. S. Paterson,  1972, unpublished; a description of Paterson's proof was given in MIT class notes (Course 6.851J) by A. R. Meyer and M. J. Fischer, 1973"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/1020067"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Andrew Chi Chih Yao,  On the average behavior of set merging algorithms (extended abstract),  Eighth Annual ACM Symposium on Theory of Computing (Hershey, Pa., 1976), Assoc. Comput. Mach., New York,  1976,  192\u2013195 55:18190365.68034","DOI":"10.1145\/800113.803648"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:15Z","timestamp":1787337735000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214010"],"URL":"https:\/\/doi.org\/10.1137\/0214010","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}