{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:59:35Z","timestamp":1725663575635},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540534143"},{"type":"electronic","value":"9783540468691"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-53414-8_43","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:02:19Z","timestamp":1330189339000},"page":"204-213","source":"Crossref","is-referenced-by-count":0,"title":["Optimal parallel 3-colouring algorithm for rooted trees and its application"],"prefix":"10.1007","author":[{"given":"Peter","family":"Raj\u010d\u00e1ni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D.G. Kirkpatrick and T. Przytycka, \"A simple parallel tree contraction algorithm\", J. Algorithms, 10 (1989), pp.287\u2013302.","journal-title":"J. Algorithms"},{"key":"17_CR2","doi-asserted-by":"publisher","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 (1988a), pp. 329\u2013346.","journal-title":"Algorithmica"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin, \"Faster optimal parallel prefix sums and list ranking\", Inform. and Comput., 81 (1989), pp.334\u2013352.","journal-title":"Inform. and Comput."},{"key":"17_CR4","volume-title":"Concurrent Computations: Algorithms, Architecture and Technology","author":"H. Gazit","year":"1988","unstructured":"H. Gazit, G.L. Miller and S.H. Teng, \"Optimal tree contraction in an EREW model\", in S.K. Tewkesbury, B.W. Dickinson and S.C. Schwartz, editors, Concurrent Computations: Algorithms, Architecture and Technology, Plenum Press, New York, 1988."},{"key":"17_CR5","volume-title":"Efficient parallel algorithms","author":"A. Gibbons","year":"1988","unstructured":"A. Gibbons and W. Rytter, \"Efficient parallel algorithms\", Cambridge University Press, Cambridge, 1988."},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0890-5401(89)90027-8","volume":"81","author":"A. Gibbons","year":"1989","unstructured":"A. Gibbons and W. Rytter, \"Optimal parallel algorithms for dynamic expression evaluation and context-free recognition\", Inform. and Comput., 81 (1989), pp.32\u201345.","journal-title":"Inform. and Comput."},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A. V. Goldberg","year":"1988","unstructured":"A. V. Goldberg, S. A. Plotkin and G. E. Shannon, \"Parallel symmetry \u2014 breaking in sparse graphs\", SIAM J. Disc. Math., 1 (1988), pp.434\u2013446.","journal-title":"SIAM J. Disc. Math."},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg and T. Spencer, \"Constructing a maximal independent set in parallel\", SIAM J. Disc. Math., 2 (1989), pp.322\u2013328.","journal-title":"SIAM J. Disc. Math."},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/BFb0040370","volume":"319","author":"T. Hagerup","year":"1988","unstructured":"T. Hagerup, \"Optimal parallel algorithms on planar graphs\", in J.H. Reif, editor, VLSI Algorithms and Architectures, Lecture Notes in Computer Science 319, Springer-Verlag, New York, Berlin, 1988, pp. 24\u201332.","journal-title":"VLSI Algorithms and Architectures, Lecture Notes in Computer Science"},{"key":"17_CR10","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":"17_CR11","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BFb0040378","volume":"319","author":"S.R. Kosaraju","year":"1988","unstructured":"S.R. Kosaraju and A.L. Delcher, \"Optimal parallel evaluation of tree \u2014 structured computations by raking\", in J.H. Reif, editor, VLSI Algorithms and Architectures, Lecture Notes in Computer Science, 319, Springer-Verlag, New York, Berlin, 1988, pp.101\u2013110.","journal-title":"VLSI Algorithms and Architectures, Lecture Notes in Computer Science"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"M. Luby, \"Removing randomness in parallel computation without a processor penalty\", in Proc. 29th Annual IEEE Symp. on Foundations of Computer Science, 1988, pp.162\u2013173.","DOI":"10.1109\/SFCS.1988.21934"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"G.L.Miller and J.H. Reif, \"Parallel tree contraction and its application\", in Proc. 26th Annual IEEE Symp. on Foundations of Computer Science, 1985, pp.478\u2013489.","DOI":"10.1109\/SFCS.1985.43"}],"container-title":["Lecture Notes in Computer Science","Aspects and Prospects of Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-53414-8_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:12:23Z","timestamp":1619557943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53414-8_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540534143","9783540468691"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-53414-8_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}