{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:13:26Z","timestamp":1762917206532},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642108761"},{"type":"electronic","value":"9783642108778"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10877-8_28","type":"book-chapter","created":{"date-parts":[[2009,12,2]],"date-time":"2009-12-02T02:11:04Z","timestamp":1259719864000},"page":"359-364","source":"Crossref","is-referenced-by-count":3,"title":["Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm"],"prefix":"10.1007","author":[{"given":"Yves","family":"M\u00e9tivier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John Michael","family":"Robson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nasser","family":"Saheb-Djahromi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akka","family":"Zemmari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"28_CR1","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1994.1002","volume":"114","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Moran, S., Warmuth, M.K.: The distributed bit complexity of the ring: from the anonymous case to the non-anonymous case. Information and computation\u00a0114(2), 34\u201350 (1994)","journal-title":"Information and computation"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: STOC, pp. 206\u2013219 (1986)","DOI":"10.1145\/12130.12151"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Moran, S., Rajsbaum, S.: Bit complexity of breaking and achieving symmetry in chains and rings. Journal of the ACM\u00a055(1) (2008)","DOI":"10.1145\/1326554.1326557"},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-004-1104-3","volume":"41","author":"I. Finocchi","year":"2004","unstructured":"Finocchi, I., Panconesi, A., Silvestri, R.: An experimental analysis of simple, distributed vertex coloring algorithms. Algorithmica\u00a041(1), 1\u201323 (2004)","journal-title":"Algorithmica"},{"key":"28_CR5","doi-asserted-by":"crossref","DOI":"10.1201\/9781420010848","volume-title":"Distributed systems - An algorithmic approach","author":"S. Ghosh","year":"2006","unstructured":"Ghosh, S.: Distributed systems - An algorithmic approach. CRC Press, Boca Raton (2006)"},{"issue":"5","key":"28_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","volume":"70","author":"\u00d6. Johansson","year":"1999","unstructured":"Johansson, \u00d6.: Simple distributed (\u0394\u2009+\u20091)-coloring of graphs. Information Processing Letters\u00a070(5), 229\u2013232 (1999)","journal-title":"Information Processing Letters"},{"key":"28_CR7","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1999","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1999)"},{"key":"28_CR8","volume-title":"Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS 2006)","author":"K. Kothapalli","year":"2006","unstructured":"Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in \n                    \n                      \n                    \n                    ${O}(\\sqrt{\\log n})$\n                   bit rounds. In: Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Rhodes Island, Greece, April 25-29. IEEE, Los Alamitos (2006)"},{"key":"28_CR9","first-page":"7","volume-title":"Proceedings of the 25 Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25 Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 7\u201315. ACM Press, New York (2006)"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021, 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"28_CR11","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M. Luby","year":"1993","unstructured":"Luby, M.: Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci.\u00a047(2), 250\u2013286 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing - A Locality-sensitive approach. In: SIAM Monographs on discrete mathematics and applications (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"28_CR13","volume-title":"Design and analysis of distributed algorithms","author":"N. Santoro","year":"2007","unstructured":"Santoro, N.: Design and analysis of distributed algorithms. Wiley, Chichester (2007)"},{"key":"28_CR14","first-page":"209","volume-title":"Proceedings of the 11th ACM Symposium on Theory of computing (STOC)","author":"A.C. Yao","year":"1979","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proceedings of the 11th ACM Symposium on Theory of computing (STOC), pp. 209\u2013213. ACM Press, New York (1979)"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10877-8_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:56:23Z","timestamp":1558270583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10877-8_28"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642108761","9783642108778"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10877-8_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}