{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:52Z","timestamp":1725664732391},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_134","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:02Z","timestamp":1330292222000},"page":"223-233","source":"Crossref","is-referenced-by-count":0,"title":["Neighborhood graphs and distributed \u0394+1-coloring"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Kelsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, A. Itai, A fast randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, pp. 567\u2013583, 1986.","journal-title":"J. Algorithms"},{"key":"20_CR2","volume-title":"The probabilistic method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J.H. Spencer, The probabilistic method, John Wiley & Sons, New York, 1992."},{"key":"20_CR3","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"B. Awerbuch, Complexity of network synchronization, JACM, 32:804\u2013823, 1985.","journal-title":"JACM"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A.V. Goldberg, M. Luby and S.A. Plotkin, Network decomposition and locality in distributed computation, Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 364\u2013369, 1989.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"J.A. Bondy and U.S.R. Murty, Graph theory with applications, North-Holland, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Inform, and Control, 70 (1986), pp. 32\u201356.","journal-title":"Inform, and Control"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"A.V. Goldberg, S. Plotkin and G.E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM J. Disc. Math, Vol. 1, No. 4, 1988.","DOI":"10.1137\/0401044"},{"key":"20_CR8","first-page":"193","volume":"21","author":"N. Linial","year":"1992","unstructured":"N. Linial, Locality in distributed graph algorithms, SJC, 21:193\u2013201, 1992.","journal-title":"SJC"},{"key":"20_CR9","first-page":"250","volume":"47","author":"M. Luby","year":"1993","unstructured":"M. Luby, Removing randomness in parallel computation without a processor penalty, JCSS, 47:250\u2013286, 1993.","journal-title":"JCSS"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Computing, vol. 15, 1986, pp. 1036\u20131053.","journal-title":"SIAM J. Computing"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"M. Naor and L. Stockmeyer, What can be computed locally?, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993.","DOI":"10.1145\/167088.167149"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"A. Panconesi and A. Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992.","DOI":"10.1145\/129712.129769"},{"key":"20_CR13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs, J. Comput. System Sci., 37:130\u2013143, 1988.","journal-title":"J. Comput. System Sci."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"M. Szegedy and S. Vishwanathan, Locality based graph coloring, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993.","DOI":"10.1145\/167088.167156"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_134.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:01Z","timestamp":1605647161000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_134","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}