{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:17Z","timestamp":1759639037285,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T00:00:00Z","timestamp":1490313600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"publisher","award":["120032011","152679-051"],"award-info":[{"award-number":["120032011","152679-051"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N011163\/1"],"award-info":[{"award-number":["EP\/N011163\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00446-017-0298-y","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T06:50:42Z","timestamp":1490338242000},"page":"69-82","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing large independent sets in a single round"],"prefix":"10.1007","volume":"31","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1802-4011","authenticated-orcid":false,"given":"Christian","family":"Konrad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"issue":"4","key":"298_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00446-012-0175-7","volume":"26","author":"Y Afek","year":"2013","unstructured":"Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distrib. Comput. 26(4), 195\u2013208 (2013)","journal-title":"Distrib. Comput."},{"issue":"4","key":"298_CR2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"298_CR3","volume-title":"The Probabilistic Method","author":"N Alon","year":"2004","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, Hoboken (2004)"},{"key":"298_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28\u201330, 1980, Los Angeles, CA, USA, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"298_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L.: On the locality of some NP-complete problems. In: Proceedings of International Colloquium on Automata, Languages, and Programming, ICALP\u201912, vol. 2, pp. 403\u2013415 (2012)","DOI":"10.1007\/978-3-642-31585-5_37"},{"key":"298_CR6","unstructured":"Barenboim, L., Elkin, M., Gavoille, C.: A fast network-decomposition algorithm and its applications to constant-time distributed computation\u2014(extended abstract). In: Structural Information and Communication Complexity\u201422nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14\u201316, 2015, Post-Proceedings, pp. 209\u2013223 (2015)"},{"key":"298_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, Marijke H.L., Halld\u00f3rsson, Magn\u00fas, M., Konrad, C., Kuhn, F.: Brief announcement: Local independent set approximation. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC \u201916, New York, NY, USA, ACM (2016)","DOI":"10.1145\/2933057.2933068"},{"key":"298_CR8","unstructured":"Caro, Y.: New results on the independence number. Technical report, Tel Aviv University (1979)"},{"key":"298_CR9","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the local model. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"298_CR10","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Kuhn, F.: Deploying wireless networks withbeeps. In: Proceedings of the 24th International Conference on Distributed Computing, DISC\u201910, pp. 148\u2013162, Springer, Berlin, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15763-9_15"},{"key":"298_CR11","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proceedings of the 22nd International Symposium on DistributedComputing, DISC \u201908, pp. 78\u201392. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"298_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201916, pp. 270\u2013277. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"298_CR13","unstructured":"Goldberg, M., Spencer, T.H.: An efficient parallel algorithm that finds independent sets of guaranteed size. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 219\u2013225 (1990)"},{"key":"298_CR14","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/s00453-015-0051-5","volume":"76","author":"BV Halld\u00f3rsson","year":"2016","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets in sparse hypergraphs. Algorithmica 76, 490\u2013501 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"298_CR15","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2390176.2390183","volume":"9","author":"MM Halld\u00f3rsson","year":"2012","unstructured":"Halld\u00f3rsson, M.M.: Wireless scheduling with power control. ACM Trans. Algorithms 9(1), 7:1\u20137:20 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"298_CR16","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Konrad, C.: Distributed algorithms for coloring interval graphs. In: Proceedings of the 28th International Conference on Distributed Computing, DISC\u201914 (2014)","DOI":"10.1007\/978-3-662-45174-8_31"},{"issue":"2","key":"298_CR17","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s00446-014-0222-7","volume":"29","author":"MM Halld\u00f3rsson","year":"2016","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Nearly optimal bounds for distributed wireless scheduling in the sinr model. Distrib. Comput. 29(2), 77\u201388 (2016)","journal-title":"Distrib. Comput."},{"issue":"1","key":"298_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$ n 1 - \u03f5 . Acta Mathematica 182(1), 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"298_CR19","unstructured":"Holzer, S., Lynch, N.: Brief announcement: beeping a maximal independent set fast. In: 30th International Symposium on Distributed Computing (DISC) (2016)"},{"issue":"5","key":"298_CR20","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00446-016-0269-8","volume":"29","author":"P Jeavons","year":"2016","unstructured":"Jeavons, P., Scott, A., Lei, X.: Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring. Distrib. Comput. 29(5), 377\u2013393 (2016)","journal-title":"Distrib. Comput."},{"key":"298_CR21","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. In: Proceedings of the 13th International Symposium on Algorithms and Computation,ISAAC \u201902, pp. 535\u2013549. Springer, London, UK (2002)","DOI":"10.1007\/3-540-36136-7_47"},{"key":"298_CR22","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, Berlin (1972)"},{"key":"298_CR23","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., V\u00f6cking, B.: Distributed contention resolution in wireless networks. In: Proceedings of the 24th International Conference on Distributed Computing, DISC\u201910, pp. 163\u2013178. Springer, Berlin, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15763-9_16"},{"issue":"2","key":"298_CR24","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/2742012","volume":"63","author":"F Kuhn","year":"2016","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17:1\u201317:44 (2016)","journal-title":"J. ACM"},{"key":"298_CR25","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributedgraph coloring. In: Proceedings of the Twenty-fifth Annual ACMSymposium on Principles of Distributed Computing, PODC \u201906, pp.7\u201315. ACM, New York, NY, USA (2006)","DOI":"10.1145\/1146381.1146387"},{"key":"298_CR26","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-hoc networksbeyond unit disk graphs. In: Proceedings of the 2003 Joint Workshopon Foundations of Mobile Computing, DIALM-POMC \u201903, pp. 69\u201378.ACM, New York, NY, USA (2003)","DOI":"10.1145\/941079.941089"},{"key":"298_CR27","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)"},{"issue":"4","key":"298_CR28","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"298_CR29","unstructured":"M\u00e9tivier, Y., Robson, J.M., Zemmari, A.: On distributed computing with beeps. CoRR (2015). arXiv:1507.02721"},{"key":"298_CR30","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201905, pp. 148\u2013157. ACM, New York, NY, USA (2005)","DOI":"10.1145\/1073814.1073842"},{"issue":"6","key":"298_CR31","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"298_CR32","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"298_CR33","doi-asserted-by":"crossref","unstructured":"Schmid, S., Wattenhofer, R.: Algorithmic models for sensor networks. In: Proceedings of the 20th International Conference on Parallel and Distributed Processing, IPDPS\u201906, pp. 177\u2013177. IEEE Computer Society, Washington, DC, USA (2006)","DOI":"10.1109\/IPDPS.2006.1639417"},{"key":"298_CR34","doi-asserted-by":"publisher","unstructured":"Schneider, J., Wattenhofer, R.: An optimal maximal independent set algorithm for bounded-independence graphs. Distrib. Comput. 22(5), 349\u2013361 (2010). doi: 10.1007\/s00446-010-0097-1","DOI":"10.1007\/s00446-010-0097-1"},{"issue":"2","key":"298_CR35","doi-asserted-by":"crossref","first-page":"24:1","DOI":"10.1145\/2431211.2431223","volume":"45","author":"J Suomela","year":"2013","unstructured":"Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24:1\u201324:40 (2013)","journal-title":"ACM Comput. Surv."},{"key":"298_CR36","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"key":"298_CR37","unstructured":"Wei, V.K.: A lower bound on the stability number of a simple graph. Technical report, Bell Laboratories (1981)"},{"issue":"1","key":"298_CR38","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0298-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0298-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0298-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:39:32Z","timestamp":1568939972000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0298-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,24]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["298"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0298-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,3,24]]}}}