{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T04:07:44Z","timestamp":1748664464074,"version":"3.41.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240237"},{"type":"electronic","value":"9783319240244"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_11","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T12:00:10Z","timestamp":1441368010000},"page":"169-182","source":"Crossref","is-referenced-by-count":1,"title":["An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Ka Wong","family":"Chong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"key":"11_CR1","volume-title":"Network Flows","author":"R Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood (1993)"},{"issue":"10","key":"11_CR2","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"36","author":"B Awerbuch","year":"1987","unstructured":"Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Comput. 36(10), 1258\u20131263 (1987)","journal-title":"IEEE Trans. Comput."},{"issue":"6","key":"11_CR3","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1137\/S0097539795289859","volume":"27","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender, H., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27(6), 1725\u20131746 (1998)","journal-title":"SIAM J. Comput."},{"key":"11_CR4","first-page":"37","volume":"3","author":"O Boruvka","year":"1926","unstructured":"Boruvka, O.: O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ca Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3, 37\u201358 (1926)","journal-title":"Pr\u00e1ca Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti"},{"issue":"6","key":"11_CR5","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D Cheriton","year":"1976","unstructured":"Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM J. Comput. 5, 724\u2013742 (1976)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"11_CR7","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1145\/358628.358650","volume":"25","author":"FY Chin","year":"1982","unstructured":"Chin, F.Y., Lam, J., Chen, I.N.: Efficient parallel algorithms for some graph problems. Commun. ACM 25(9), 659\u2013665 (1982)","journal-title":"Commun. ACM"},{"key":"11_CR8","unstructured":"Chong, K.W.: Finding minimum spanning trees on the EREW PRAM. In: Proceedings of the International Computer Symposium\u2014ICS\u201996, pp. 7\u201314. Taiwan (1996)"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1006\/jagm.1995.1016","volume":"18","author":"KW Chong","year":"1995","unstructured":"Chong, K.W., Lam, T.W.: Finding connected components in $$O(\\log n\\log \\log n)$$ time on the EREW PRAM. J. Algorithms 18, 378\u2013402 (1995)","journal-title":"J. Algorithms"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1145\/375827.375847","volume":"48","author":"KW Chong","year":"2001","unstructured":"Chong, K.W., He, Y., Lam, T.W.: Concurrent threads and optimal parallel minimum spanning trees algorithm. J. ACM 48(2), 297\u2013323 (2001)","journal-title":"J. ACM"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R., Klein, P.N., Tarjan, R.E.: Finding minimum spanning forests in logarithmic time and linear work using random sampling. In: Proceedings of the 8th ACM symposium on Parallel Algorithms and Architectures (ACM), pp. 243\u2013250 (1996)","DOI":"10.1145\/237502.237563"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70, 32\u201353 (1986)","journal-title":"Inf. Control"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Approximate and exact parallel scheduling with applications to list, tree and graph problems. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 478\u2013491. IEEE (1986)","DOI":"10.1109\/SFCS.1986.10"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M Fredman","year":"1994","unstructured":"Fredman, M., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"11_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H Gabow","year":"1986","unstructured":"Gabow, H., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A Goldberg","year":"1988","unstructured":"Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discrete Math. 1, 434\u2013446 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0890-5401(90)90034-F","volume":"84","author":"T Hagerup","year":"1990","unstructured":"Hagerup, T.: Optimal parallel algorithms on planar graphs. Inf. Comput. 84, 71\u201396 (1990)","journal-title":"Inf. Comput."},{"key":"11_CR18","unstructured":"Hagerup, T.: Optimal Parallel Computation of Minimum Spanning Forests in Planar Graphs, Technical Report 11\/1990. Universit\u00e4t des Saarlandes, May 1990"},{"issue":"2","key":"11_CR19","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/0218020","volume":"18","author":"T Hagerup","year":"1989","unstructured":"Hagerup, T., Chrobak, M., Diks, K.: Optimal parallel 5-colouring of planar graphs. SIAM J. Comput. 18(2), 288\u2013300 (1989)","journal-title":"SIAM J. Comput."},{"key":"11_CR20","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)"},{"key":"11_CR21","volume-title":"An Introduction to Parallel Algorithms","author":"J J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reding (1992)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Johnson, D.B., Metaxas, P.: Connected components in $$O(\\log ^{3\/2}|V|)$$ parallel time for the CREW PRAM. In: Proceeings of 32nd IEEE Symposium on Foundations of Computer Science, pp. 688\u2013695, IEEE (1991)","DOI":"10.1109\/SFCS.1991.185437"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1006\/jagm.1995.1043","volume":"19","author":"DB Johnson","year":"1995","unstructured":"Johnson, D.B., Metaxas, P.: A parallel algorithm for computing minimum spanning trees. J. Algorithms 19, 383\u2013401 (1995)","journal-title":"J. Algorithms"},{"key":"11_CR24","unstructured":"Karger, D.R.: Approximating, verifying, and constructing minimum spanning trees. Unpublished manuscript (1992)"},{"issue":"2","key":"11_CR25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321\u2013328 (1995)","journal-title":"J. ACM"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Karp, R., Ramachandran, V.: Parallel Algorithms for Shared-Memory Machines. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. A, pp. 869\u2013941. Elsevier, Amsterdam (1990)","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"issue":"1","key":"11_CR27","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16\u201334 (2002)","journal-title":"J. ACM"},{"issue":"6","key":"11_CR28","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1137\/S0097539700371065","volume":"31","author":"S Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SIAM J. Comput. 31(6), 1879\u20131895 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR29","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1142\/S012962649700005X","volume":"7","author":"CD Zaroliagis","year":"1997","unstructured":"Zaroliagis, C.D.: Simple and work-efficient parallel algorithms for the minimum spanning tree problem. Parallel Process. Lett. 7(1), 25\u201337 (1997)","journal-title":"Parallel Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T12:20:57Z","timestamp":1748607657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}