{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:51Z","timestamp":1725664251282},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580782"},{"type":"electronic","value":"9783540484356"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58078-6_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:10:55Z","timestamp":1330269055000},"page":"13-22","source":"Crossref","is-referenced-by-count":2,"title":["Optimal parallel verification of minimum spanning trees in logarithmic time"],"prefix":"10.1007","author":[{"given":"Brandon","family":"Dixon","sequence":"first","affiliation":[]},{"given":"Robert E.","family":"Tkrjan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"2_CR1","unstructured":"N. Alon and B. Schieber Optimal preprocessing for answering on-line product queries, Unpublished manuscript"},{"issue":"No.10","key":"2_CR2","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"C-36","author":"B. Awerbuch","year":"1987","unstructured":"B. Awerbuch and Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Trans. on Computers, Vol. C-36, No. 10, Oct. 1987, pp. 1258\u20131263","journal-title":"IEEE Trans. on Computers"},{"key":"2_CR3","unstructured":"H. Booth and J. Westbrook, Linear Algorithms for Analysis of Minimum Spanning and Shortest Path Trees in Planar Graphs, Yale University, Department of Computer Science, TR-768, Feb. 1990."},{"issue":"6","key":"2_CR4","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. D. Dixon","year":"1992","unstructured":"B. D. Dixon, M. Rauch, and R. E. Tarjan, Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time, SIAM J. Comput. 21(6) (1992) pp. 1184\u20131192.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"H.N. Gabow, Z. Galil, T. Spencer, and R.E. Tarjan, Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs, Combinatorica 6(2) (1986) pp. 109\u2013122.","journal-title":"Combinatorica"},{"issue":"2","key":"2_CR6","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R.E. Tarjan, Fast Algorithms for Finding Nearest Common Ancestors, SIAM J. Comput. 13(2) (1984) pp. 338\u2013355.","journal-title":"SIAM J. Comput."},{"key":"2_CR7","unstructured":"P. Klein and R.E. Tarjan, A Randomized Linear Time Algorithm for Finding Minimum Spanning Trees, Personal comunication."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"D. B. Johnson and P. Metaxas, A parallel algorithm for computing minimum spanning trees, 4th ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 363\u2013372.","DOI":"10.1145\/140901.141917"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran, Parallel Algorithms for Shared Memory Machines, Handbook of Theoretical Computer Science (1990) Chapter 17.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"2_CR10","first-page":"496","volume":"26","author":"J. H. Reif","year":"1985","unstructured":"J. H. Reif, An Optimal parallel algorithm for integer sorting, Proc. STOC 26 (1985) 496\u2013504.","journal-title":"Proc. STOC"},{"issue":"6","key":"2_CR11","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization, SIAM J. Comput. 17(6) (1988) pp. 1253\u20131262.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR12","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"R.E. Tarjan, Applications of Path Compressions on Balanced Trees, J. Assoc. Comput. Mach. 26(4) (1979) pp. 690\u2013715.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"2_CR13","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R.E. Tarjan","year":"1982","unstructured":"R.E. Tarjan, Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees, Information Processing Letters 14(1) (1982) pp. 30\u201333. Corrigendum, Ibid 23 (1986), p.219.","journal-title":"Information Processing Letters"},{"key":"2_CR14","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"R.E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."}],"container-title":["Lecture Notes in Computer Science","Parallel and Distributed Computing Theory and Practice"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58078-6_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:16:45Z","timestamp":1605647805000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58078-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580782","9783540484356"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-58078-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}