{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:38:20Z","timestamp":1794339500259,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540584346","type":"print"},{"value":"9783540487944","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049420","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T13:42:35Z","timestamp":1141652555000},"page":"331-342","source":"Crossref","is-referenced-by-count":5,"title":["An o(n) work EREW parallel algorithm for updating MST"],"prefix":"10.1007","author":[{"given":"Sajal K.","family":"Das","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Ferragina","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","volume":"29","author":"M. Atallah","year":"1984","unstructured":"M. Atallah and U. Vishkin. Finding Euler tours in parallel. Journal of computer and system sciences, 29:330\u2013337, 1984.","journal-title":"Journal of computer and system sciences"},{"key":"30_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0022-0000(78)90022-3","volume":"16","author":"F. Chin","year":"1978","unstructured":"F. Chin and D. Houck. Algorithms for updating minimum spanning trees. Journal of Computer and System Science, 16:333\u2013344, 1978.","journal-title":"Journal of Computer and System Science"},{"key":"30_CR3","volume-title":"Technical Report CRPDC-94-8","author":"S. K. Das","year":"1994","unstructured":"S. K. Das and P. Ferragina. A fully-dynamic EREW parallel algorithm for updating MST. Technical Report CRPDC-94-8, Dept. of Computer Science, University of North Texas, Denton, May 1994."},{"key":"30_CR4","volume-title":"TR 93-20","author":"D. Eppstein","year":"1993","unstructured":"D. Eppstein, Z. Galil, and G. F. Italiano. Improved sparsification. In TR 93-20. Dept. of Information and Computer Science, University of California, Irvine, 1993."},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification \u2014 a technique for speeding up Dynamic Graph Algorithms. Proc. of IEEE Symposium on Foundations of Computer Science, 60\u201369, 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"P. Ferragina and F. Luccio. Batch dynamic algorithms for two graph problems. In Proc. PARLE '94, Lecture Notes in Computer Science, to appear, 1994.","DOI":"10.1007\/3-540-58184-7_143"},{"key":"30_CR7","volume-title":"Technical Report 8\/94","author":"P. Ferragina","year":"1994","unstructured":"P. Ferragina. Parallel dynamic edge deletion for MST. Technical Report 8\/94, Dipartimento di Informatica, Universit\u00e0 di Pisa, Italy, June 1994."},{"issue":"4","key":"30_CR8","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Computing, 14(4):781\u2013798, 1985.","journal-title":"SIAM J. Computing"},{"key":"30_CR9","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. H. Spencer, and R. E. Tarjan. Efficient algorithms for minimum spanning trees on directed and undirected graphs. Combinatorica, 6:109\u2013122, 1986.","journal-title":"Combinatorica"},{"key":"30_CR10","unstructured":"J. J\u00e1 J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"30_CR11","unstructured":"D. B. Johnson and P. Metaxas. Optimal parallel and sequential algorithms for the vertex updating problem of a minimum spanning tree. Technical Report PCS-TR91-159, Dartmouth College, Dept. of Mathematics and Computer Science, 1991."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"D. B. Johnson and P. Metaxas. A parallel algorithm for computing minimum spanning trees. In Proc. ACM Symposium on Parallel Algorithm and Architectures, pp. 363\u2013372, 1992.","DOI":"10.1145\/140901.141917"},{"issue":"5","key":"30_CR13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0020-0190(88)90084-1","volume":"27","author":"H. Jung","year":"1988","unstructured":"H. Jung and K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees. Information Processing Letters, 27(5):227\u2013236, 1988.","journal-title":"Information Processing Letters"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF01228509","volume":"9","author":"S. Pawagi","year":"1993","unstructured":"S. Pawagi and O. Kaser. Optimal parallel algorithms for multiple updates of minimum spanning trees. Algorithmica, 9:357\u2013382, 1993.","journal-title":"Algorithmica"},{"issue":"5","key":"30_CR15","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0020-0190(86)90098-0","volume":"22","author":"S. Pawagi","year":"1986","unstructured":"S. Pawagi and I. V. Ramakrishnan. An O(log n) algorithm for parallel update of minimum spanning trees. Information Processing Letters, 22(5):223\u2013229, 1986.","journal-title":"Information Processing Letters"},{"key":"30_CR16","volume-title":"Technical Report COMP-TR90-140","author":"A. Sch\u00e1ffer","year":"1990","unstructured":"A. Sch\u00e1ffer and P. Varman. Parallel batch update of minimum spanning trees. Technical Report COMP-TR90-140, Rice University, Houston, Texas, 1990."},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"X. Shen and W. Liang. A parallel algorithm for multiple edge updates of minimum spanning trees. In Proc. International Parallel Processing Symposium, 310\u2013317, 1993.","DOI":"10.1109\/IPPS.1993.262898"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0204032","volume":"4","author":"P. Spira","year":"1975","unstructured":"P. Spira and A. Pan. On finding and updating spanning trees and shortest paths. SIAM Journal of Computing, 4:375\u2013380, 1975.","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,9]],"date-time":"2019-02-09T16:56:09Z","timestamp":1549731369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0049420","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0049390","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}