{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T22:50:19Z","timestamp":1790635819562,"version":"4.1.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T00:00:00Z","timestamp":1346112000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00446-012-0175-7","type":"journal-article","created":{"date-parts":[[2012,8,27]],"date-time":"2012-08-27T07:16:20Z","timestamp":1346051780000},"page":"195-208","source":"Crossref","is-referenced-by-count":54,"title":["Beeping a maximal independent set"],"prefix":"10.1007","volume":"26","author":[{"given":"Yehuda","family":"Afek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noga","family":"Alon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziv","family":"Bar-Joseph","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alejandro","family":"Cornejo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,8,28]]},"reference":[{"key":"175_CR1","doi-asserted-by":"crossref","unstructured":"Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183\u2013185 (2011)","DOI":"10.1126\/science.1193210"},{"key":"175_CR2","doi-asserted-by":"crossref","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)","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"175_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proc. of the 30th Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"175_CR4","unstructured":"Chlebus, B., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. In: Prof. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 861\u2013870 (2000)"},{"issue":"4","key":"175_CR5","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1006\/jtbi.1996.0233","volume":"183","author":"JR Collier","year":"1996","unstructured":"Collier, J.R., Monk, N.A., Maini, P.K., Lewis, J.H.: Pattern formation by lateral inhibition with feedback: a mathematical model of delta-notch intercellular signalling. J. Theor. Biol. 183(4), 429\u2013446 (1996)","journal-title":"J. Theor. Biol."},{"key":"175_CR6","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Proc. 24th Symposium on Distributed Computing (DISC), pp. 148\u2013162 (2010)","DOI":"10.1007\/978-3-642-15763-9_15"},{"key":"175_CR7","doi-asserted-by":"crossref","unstructured":"Degesys, J., Rose, I., Patel, A., Nagpal, R.: Desync: self-organizing desynchronization and TDMA on wireless sensor networks. In: Prof. 6th Conf. on Information Processing in Sensor Networks (IPSN), p. 20 (2007)","DOI":"10.1145\/1236360.1236363"},{"key":"175_CR8","doi-asserted-by":"crossref","unstructured":"Flury, R., Wattenhofer, R.: Slotted programming for sensor networks. In: Proc. 9th Conference on Information Processing in Sensor Networks (IPSN) (2010)","DOI":"10.1145\/1791212.1791216"},{"key":"175_CR9","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2010.01.004","volume":"411","author":"D Ilcinkas","year":"2010","unstructured":"Ilcinkas, D., Kowalski, D., Pelc, A.: Fast radio broadcasting with advice. Theor. Comput. Sci. 411, 14\u201315 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"175_CR10","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proc. 19th International Symposium on, Distributed Computing (DISC\u201905), pp. 273\u2013287 (2005)","DOI":"10.1007\/11561927_21"},{"key":"175_CR11","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"175_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer R.: The price of being near-sighted. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"175_CR13","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, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"175_CR14","unstructured":"M\u00e9tivier, Y., Michael Robson, J., Saheb-Djahromi, N., Zemmari, A.: An optimal bit complexity randomized distributed mis algorithm. Distrib. Comput. 23, 331\u2013340 (2011)"},{"key":"175_CR15","unstructured":"Moscibroda, T., Wattenhofer, R.: Efficient computation of maximal independent sets in structured multi-hop radio networks. In: Proc. of 1st International Conference on Mobile Ad Hoc Sensor Systems (MASS) (2004)"},{"key":"175_CR16","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proc. 24th Symposium on Principles of Distributed Computing (PODC) (2005)","DOI":"10.1145\/1073814.1073842"},{"key":"175_CR17","doi-asserted-by":"crossref","unstructured":"Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.: Lightweight coloring and desynchronization for networks. In: Proc. 28th IEEE Conf. on Computer Communications (INFOCOM) (2009)","DOI":"10.1109\/INFCOM.2009.5062165"},{"issue":"2","key":"175_CR18","first-page":"581","volume":"20","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581\u2013592 (1995)","journal-title":"J. Algorithms"},{"key":"175_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: a locality-sensitive approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"175_CR20","doi-asserted-by":"crossref","unstructured":"Scheideler, C., Richa, A., Santi, P.: An $${O}(\\log n)$$ dominating set protocol for wireless ad-hoc networks under the physical interference model. In: Proc. 9th Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC) (2008)","DOI":"10.1145\/1374618.1374632"},{"key":"175_CR21","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A Log-Star Maximal Independent Set Algorithm for Growth-Bounded Graphs. In: Proc. 28th Symposium on Principles of Distributed Computing (PODC) (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"175_CR22","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: What is the use of collision detection (in wireless networks)? In: Proc. of 24th Symposium on Distributed Computing (DISC) (2010)","DOI":"10.1007\/978-3-642-15763-9_14"},{"key":"175_CR23","unstructured":"Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw. Appl. 6343, 133\u2013147 (2004)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0175-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-012-0175-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0175-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T04:24:02Z","timestamp":1562127842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-012-0175-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,28]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["175"],"URL":"https:\/\/doi.org\/10.1007\/s00446-012-0175-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,28]]}}}