{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:22:46Z","timestamp":1746264166133},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,4,1]],"date-time":"1993-04-01T00:00:00Z","timestamp":733622400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,4]]},"DOI":"10.1007\/bf01228509","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T19:18:45Z","timestamp":1109359125000},"page":"357-381","source":"Crossref","is-referenced-by-count":16,"title":["Optimal parallel algorithms for multiple updates of minimum spanning trees"],"prefix":"10.1007","volume":"9","author":[{"given":"Shaunak","family":"Pawagi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Owen","family":"Kaser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","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,J. Comput. System Sci.,16 (1978), 333?344.","journal-title":"J. Comput. System Sci."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/358628.358650","volume":"25","author":"F. Chin","year":"1982","unstructured":"F. Chin, J. Lam, and I. Chen, Efficient Parallel Algorithms for Some Graph Problems,Comm. ACM,25(1982), 170?175.","journal-title":"Comm. ACM"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01762121","volume":"3","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time,Algorithmica,3 (1988), 329?346.","journal-title":"Algorithmica"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, Approximate Parallel Scheduling, Part I.SIAM J. Comput.,17 (1988), 128?142.","journal-title":"SIAM J. Comput."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. Frederickson","year":"1985","unstructured":"G. Frederickson, Data Structure for On-line Updating of Minimum Spanning Trees,SIAM J. Comput.,14 (1985), 781?798.","journal-title":"SIAM J. Comput."},{"key":"CR6","unstructured":"H. Gazit, G. L. Miller, and S. H. Teng, Optimal Tree Contraction in the EREW Model, Extended abstract, 1986."},{"key":"CR7","volume-title":"Parallel Algorithms for Computing Maximum Independent Set in Trees and for Updating Minimum Spanning Trees, Technical Report 01","author":"H. Jung","year":"1987","unstructured":"H. Jung and K. Mehlhorn, Parallel Algorithms for Computing Maximum Independent Set in Trees and for Updating Minimum Spanning Trees, Technical Report 01, University of Saarlandes, Saarbrucken, 1987."},{"key":"CR8","volume-title":"Dynamic Tree Contraction and Its Application to Optimal Parallel Updates of Minimum Spanning Trees, Technical Report 25","author":"O. Kaser","year":"1990","unstructured":"O. Kaser and S. Pawagi, Dynamic Tree Contraction and Its Application to Optimal Parallel Updates of Minimum Spanning Trees, Technical Report 25, Department of Computer Science, State University of New York, Stony Brook, 1990."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J. B. Kruskal","year":"1956","unstructured":"J. B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,Proc. Amer. Math. Soc,7 (1956), 48?50.","journal-title":"Proc. Amer. Math. Soc"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01840376","volume":"5","author":"C. P. Kruskal","year":"1990","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, Efficient Parallel Algorithms for Graph Problems,Algorithmica,5 (1990), 43?64.","journal-title":"Algorithmica"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif, Parallel Tree Contraction and Its Applications,Proc. Twenty-Fifth Annual Symposium on Foundations of Computer Science, 1985, pp. 478?489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"CR12","unstructured":"S. Pawagi, A Parallel Algorithm for Multiple Updates of Minimum Spanning Trees,Proc. Eighteenth International Conference of Parallel Processing, 1989, pp. III.9?15."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"S. Pawagi and I. V. Ramakrishnan, Parallel Update of Graph Properties in Logarithmic Time,Proc. Fourteenth International Conference on Parallel Processing, 1985, pp. 186?193.","DOI":"10.21236\/ADA150497"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(86)90098-0","volume":"22","author":"S. Pawagi","year":"1986","unstructured":"S. Pawagi and I. V. Ramarkrishnan, An0(logn) Algorithm for Parallel Update of Minimum Spanning Trees,Inform. Process. Lett.,22 (1986), 223?229.","journal-title":"Inform. Process. Lett."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. Prim","year":"1957","unstructured":"R. Prim, Shortest Interconnection Networks and Some Generalizations,Bell System Tech. J.,36 (1957), 1389?1401.","journal-title":"Bell System Tech. J."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0218041","volume":"18","author":"S. Rajasekaran","year":"1989","unstructured":"S. Rajasekaran and J. H. Reif, Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms,SIAM J. Comput.,18 (1989), 594?607.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1137\/0210051","volume":"10","author":"C. Savage","year":"1981","unstructured":"C. Savage and J. Ja'Ja', Fast Efficient Parallel Algorithms for Some Graph Problems,SIAM J. Comput.,10 (1981), 682?691.","journal-title":"SIAM J. Comput."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, AnO(logn) Parallel Connectivity Algorithm,J. Algorithms,3 (1982), 57?67.","journal-title":"J. Algorithms"},{"key":"CR19","doi-asserted-by":"crossref","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 J. Comput.,4 (1975), 375?380.","journal-title":"SIAM J. Comput."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin, Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time,SIAM J. Conput.,14 (1985), 862?874.","journal-title":"SIAM J. Conput."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(88)90020-8","volume":"27","author":"Y. H. Tsin","year":"1988","unstructured":"Y. H. Tsin, On Handling Vertex Deletion in Updating Minimum Spanning Trees,Inform. Process. Lett.,27 (1988), 167?168.","journal-title":"Inform. Process. Lett."},{"key":"CR22","unstructured":"Y. H. Tsin, Private communication, 1990."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0304-3975(88)90035-7","volume":"58","author":"P. Varman","year":"1988","unstructured":"P. Varman and K. Doshi, A Parallel Vertex Insertion Algorithm for Minimum Spanning Trees,Theoret. Comput. Sci.,58 (1988), 379?397.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228509.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01228509\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T23:35:54Z","timestamp":1586129754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01228509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["BF01228509"],"URL":"https:\/\/doi.org\/10.1007\/bf01228509","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}