{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T07:40:59Z","timestamp":1743147659751,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642160226"},{"type":"electronic","value":"9783642160233"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16023-3_26","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T20:41:49Z","timestamp":1284928909000},"page":"303-318","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Low Memory Distributed Protocols for 2-Coloring"],"prefix":"10.1007","author":[{"given":"Amos","family":"Israeli","sequence":"first","affiliation":[]},{"given":"Mathew D.","family":"McCubbins","sequence":"additional","affiliation":[]},{"given":"Ramamohan","family":"Paturi","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Vattani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,20]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In: FOCS 1979, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"26_CR2","unstructured":"Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs, http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html"},{"key":"26_CR3","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing; Fundamentals, Simulations and Advanced Topics","author":"H. Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing; Fundamentals, Simulations and Advanced Topics, 2nd edn. John Wiley & Sons, Chichester (2004)","edition":"2"},{"issue":"5439","key":"26_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of Scaling in Random Networks. Science\u00a0286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B., Riordan, O., Spencer, J., Tusn\u00e1dy, G.: The degree sequence of a scale-free random graph process. Random Structures & Algorithms\u00a018(3) (May 2001)","DOI":"10.1002\/rsa.1009"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1007\/978-3-540-92185-1_58","volume-title":"Internet and Network Economics","author":"K. Chaudhuri","year":"2008","unstructured":"Chaudhuri, K., Chung Graham, F., Jamall, M.S.: A network coloring game. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 522\u2013530. Springer, Heidelberg (2008)"},{"issue":"4","key":"26_CR7","doi-asserted-by":"publisher","first-page":"1738","DOI":"10.1137\/080729542","volume":"23","author":"C. Cooper","year":"2009","unstructured":"Cooper, C., Frieze, A., Radzik, T.: Multiple random walks in random regular graphs. SIAM Journal on Discrete Mathematics\u00a023(4), 1738\u20131761 (2009)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"26_CR8","unstructured":"Enemark, D., McCubbins, M., Paturi, R., Weller, N.: Good edge, bad edge: How network structure affects a group\u2019s ability to coordinate. In: ESORICS (March 2009)"},{"key":"26_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Israeli, A., Jalfon, M.: Token Management Schemes and Random Walks Yield Self-Stabilizing Mutual Exclusion. In: PODC 1990, pp. 119\u2013131 (1990)","DOI":"10.1145\/93385.93409"},{"issue":"5788","key":"26_CR11","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.1127207","volume":"313","author":"M. Kearns","year":"2006","unstructured":"Kearns, M., Suri, S., Montfort, N.: An experimental study of the coloring problem on human subject networks. Science\u00a0313(5788), 824\u2013827 (2006)","journal-title":"Science"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Kearns, M., Judd, S., Tan, J., Wortman, J.: Behavioral experiments on biased voting in networks. National Academy of Science (January 2009)","DOI":"10.1073\/pnas.0808147106"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: FOCS 2001, pp. 600\u2013609 (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"issue":"6","key":"26_CR14","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1037\/0022-3514.70.6.1218","volume":"70","author":"B. Latan\u00e9","year":"1996","unstructured":"Latan\u00e9, B., L\u2019Herrou, T.: Spatial clustering in the conformity game: Dynamic social impact in electronic groups. Journal of Personality and Social Psychology\u00a070(6), 1218\u20131230 (1996)","journal-title":"Journal of Personality and Social Psychology"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1177\/1532673X09337184","volume":"37","author":"M.D. McCubbins","year":"2009","unstructured":"McCubbins, M.D., Paturi, R., Weller, N.: Connected Coordination: Network Structure and Group Coordination. American Politics Research\u00a037, 899\u2013920 (2009)","journal-title":"American Politics Research"},{"key":"26_CR16","unstructured":"Mossel, E., Schoenebeck, G.: Reaching Consensus on Social Networks. In: Innovations in Computer Science, ICS (2009)"},{"key":"26_CR17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locally-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locally-Sensitive Approach. SIAM Monographs, Philadelphia (2000)"},{"key":"26_CR18","volume-title":"Design and Analysis of Distributed Algorithms","author":"N. Santoro","year":"2007","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms. John Wiley & Sons, Inc., Chichester (2007)"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16023-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T16:07:06Z","timestamp":1711814826000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-16023-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642160226","9783642160233"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16023-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]},"assertion":[{"value":"20 September 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}