{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T07:13:06Z","timestamp":1673075586880},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540160427","type":"print"},{"value":"9783540397229","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1985]]},"DOI":"10.1007\/3-540-16042-6_27","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:32:56Z","timestamp":1330194776000},"page":"477-495","source":"Crossref","is-referenced-by-count":3,"title":["O(1) parallel time incremental graph algorithms"],"prefix":"10.1007","author":[{"given":"Deepak D.","family":"Sherlekar","sequence":"first","affiliation":[]},{"given":"Shaunak","family":"Pawagi","sequence":"additional","affiliation":[]},{"given":"I. V.","family":"Ramakrishnan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"27_CR1","volume-title":"Incremental Algorithms in Graph Theory","author":"G. Cheston","year":"1976","unstructured":"G. Cheston, \u201cIncremental Algorithms in Graph Theory\u201d, TR 91 (1976), Dept. of Computer Science, Univ. of Toronto, Toronto."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0022-0000(78)90022-3","volume":"16","author":"F. Chin","year":"1978","unstructured":"F. Chin and D. Houck, \u201cAlgorithms for Updating Minimum Spanning Trees\u201d, Journal of Computer and System Sciences, 16 (1978), pp. 333\u2013344.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"S. Cook and C. Dwork, \u201cBounds on the Time for Parallel RAMs to Compute Simple Functions\u201d, Proc. 14th ACM Symposium on Theory of Computing, 1982, pp. 231\u2013233.","DOI":"10.1145\/800070.802196"},{"key":"27_CR4","first-page":"1","volume":"28","author":"S. Even","year":"1982","unstructured":"S. Even and Y. Shlloach, \u201cAn On-line Edge Deletion Problem\u201d, Journal of ACM, 28 (1982), pp. 1\u20134.","journal-title":"Journal of ACM"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"G. Frederickson, \u201cData Structures for On-line Updating of Minimum Spanning Trees\u201d, Proc. 15th ACM Symposium on Theory of Computing (1983), pp. 252\u2013257.","DOI":"10.1145\/800061.808754"},{"key":"27_CR6","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(83)90033-9","volume":"16","author":"T. Ibaraki","year":"1983","unstructured":"T. Ibaraki and N. Katoh, \u201cOn-line Computation of Transitive Closure of Graphs\u201d, Information Processing Letters, 16 (1983), pp 95\u201397.","journal-title":"Information Processing Letters"},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Kucera","year":"1982","unstructured":"L. Kucera, \u201cParallel Computation and Conflicts in Memory Access\u201d, Information Processing Letters, 14 (1982), pp. 93\u201396.","journal-title":"Information Processing Letters"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0020-0190(82)90131-4","volume":"14","author":"D. Nath","year":"1982","unstructured":"D. Nath and S.N. Maheshwari, \u201cParallel Algorithms for the Connected Components and Minimal Spanning Tree Problems\u201d, Information Processing Letters, 14 (1982), pp. 7\u201310.","journal-title":"Information Processing Letters"},{"key":"27_CR10","unstructured":"S. Pawagi and I.V. Ramakrishnan, \u201cAn O(logn) Algorithm for Parallel Updates of Minimum Spanning Trees\u201d, Information Processing Letters, (to appear)."},{"key":"27_CR11","volume-title":"Parallel Updates of Graph Properties in Logarithmic Time","author":"S. Pawagl","year":"1985","unstructured":"S. Pawagl and I.V. Ramakrishnan, \u201cParallel Updates of Graph Properties in Logarithmic Time\u201d, Proc. 14th International Conference on Parallel Processing (1985), St. Charles, Illinois."},{"key":"27_CR12","volume-title":"Parallel Algorithms for Some Graph Problems","author":"C. Savage","year":"1977","unstructured":"C. Savage, \u201cParallel Algorithms for Some Graph Problems\u201d, TR-784 (1977), Dept. of Mathematics, Univ. of Illinois, Urbana."},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/0210051","volume":"10","author":"C. Savage","year":"1981","unstructured":"C. Savage and J. Ja'Ja', \u201cFast Efficient Parallel Algorithms for Some Graph Problems\u201d, SIAM Journal on Computing, 10 (1981), pp. 682\u2013691.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0204032","volume":"4","author":"P. Spira","year":"1975","unstructured":"P. Spira and A. Pan, \u201cOn Finding and Updating Spanning Trees and Shortest Paths\u201d, SIAM Journal on Computing, 4 (1975), pp. 375\u2013380.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR15","unstructured":"D.D. Sherlekar, S. Pawagi and I.V. Ramakrishnan, \u201cFast Incremental Parallel Algorithms for Graph Problems on PRAMs\u201d, Technical Report, U. of Maryland, 1985 (in preparation)."},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, \u201cFinding the Maximum, Merging and Sorting in a Parallel Computation Model\u201d, Journal of Algorithms, 2 (1981), pp. 88\u2013102.","journal-title":"Journal of Algorithms"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, \u201cAn O(logn) Parallel Connectivity Algorithm\u201d, Journal of Algorithms, 3 (1982), 57\u201363.","journal-title":"Journal of Algorithms"},{"key":"27_CR18","unstructured":"R.E. Tarjan and U. Vishkin, \u201cFinding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time\u201d, Proc. 23rd Annual Symp. on Foundations of Computer Science (1984), pp. 12\u201320."},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1137\/0213036","volume":"14","author":"Y. Tsin","year":"1984","unstructured":"Y. Tsin and F. Chin, \u201cEfficient Parallel Algorithms for a Class of Graph Theoretic Problems\u201d, SIAM Journal on Computing, 14 (1984), pp. 580\u2013599.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR20","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Vallant","year":"1975","unstructured":"L.G. Vallant, \u201cParallelism in Comparison Problems\u201d, SIAM Journal on Computing, 4 (1975), pp. 348\u2013355.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0196-6774(83)90033-0","volume":"4","author":"U. Vishkin","year":"1983","unstructured":"U. Vishkin, \u201cImplementation of simultaneous Memory Access in Models That Forbid it\u201d, Journal of Algorithms, 4 (1983), pp. 45\u201350.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16042-6_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:09:37Z","timestamp":1605643777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16042-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985]]},"ISBN":["9783540160427","9783540397229"],"references-count":21,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-16042-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985]]}}}