{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:03:14Z","timestamp":1783576994977,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T00:00:00Z","timestamp":1651881600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T00:00:00Z","timestamp":1651881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00446-022-00426-w","type":"journal-article","created":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T05:02:35Z","timestamp":1651899755000},"page":"373-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks"],"prefix":"10.1007","volume":"36","author":[{"given":"Varsha","family":"Dani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aayush","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas P.","family":"Hayes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,5,7]]},"reference":[{"issue":"2","key":"426_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02259748","volume":"5","author":"R Bar-Yehuda","year":"1991","unstructured":"Bar-Yehuda, R., Goldreich, O., Itai, A.: Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distrib. Comput. 5(2), 67\u201371 (1991)","journal-title":"Distrib. Comput."},{"issue":"1","key":"426_CR2","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","volume":"45","author":"R Bar-Yehuda","year":"1992","unstructured":"Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45(1), 104\u2013126 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"426_CR3","doi-asserted-by":"crossref","unstructured":"Barnes, M., Conway, C., Mathews, J., Arvind, D.K.: Ens: an energy harvesting wireless sensor network platform. In: 2010 Fifth International Conference on Systems and Networks Communications, pp. 83\u201387. IEEE (2010)","DOI":"10.1109\/ICSNC.2010.18"},{"issue":"5","key":"426_CR4","doi-asserted-by":"publisher","first-page":"1735","DOI":"10.1137\/17M1158604","volume":"47","author":"MA Bender","year":"2018","unstructured":"Bender, M.A., Kopelowitz, T., Pettie, S., Young, M.: Contention resolution with constant throughput and log-logstar channel accesses. SIAM J. Comput. 47(5), 1735\u20131754 (2018)","journal-title":"SIAM J. Comput."},{"key":"426_CR5","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Dani, V., Hayes, T.P., He, Q., Li, W., Pettie, S.: The energy complexity of broadcast. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 95\u2013104 (2018)","DOI":"10.1145\/3212734.3212774"},{"key":"426_CR6","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Dani, V., Hayes, T.P., Pettie, S.: The energy complexity of BFS in radio networks. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 273\u2013282 (2020)","DOI":"10.1145\/3382734.3405713"},{"key":"426_CR7","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Duan, R., Jiang, S.: Near-optimal time-energy trade-offs for deterministic leader election. In: Proceedings 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 162\u2013172 (2021)","DOI":"10.1145\/3409964.3461830"},{"issue":"4","key":"426_CR8","doi-asserted-by":"publisher","first-page":"49:1","DOI":"10.1145\/3341111","volume":"15","author":"Y-J Chang","year":"2019","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S., Wang, R., Zhan, W.: Exponential separations in the energy complexity of leader election. ACM Trans. Algorithms 15(4), 49:1-49:31 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"426_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Gmyr, R., Pandurangan, G.: Sleeping is efficient: Mis in $$o(1)$$-rounds node-averaged awake complexity. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 99\u2013108 (2020)","DOI":"10.1145\/3382734.3405718"},{"issue":"8","key":"426_CR10","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1016\/j.jcss.2016.05.001","volume":"82","author":"A Czygrinow","year":"2016","unstructured":"Czygrinow, A., Han\u0107kowiak, M., Szyma\u0144ska, E., Wawrzyniak, W.: On the distributed complexity of the semi-matching problem. J. Comput. Syst. Sci. 82(8), 1251\u20131267 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"426_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2529989","volume":"61","author":"R Duan","year":"2014","unstructured":"Duan, R., Pettie, S.: Linear-time approximation for maximum weight matching. J. ACM 61(1), 1\u201323 (2014)","journal-title":"J. ACM"},{"issue":"1","key":"426_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jalgor.2005.01.003","volume":"59","author":"NJA Harvey","year":"2006","unstructured":"Harvey, N.J.A., Ladner, R.E., Lov\u00e1sz, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59(1), 53\u201378 (2006)","journal-title":"J. Algorithms"},{"key":"426_CR13","doi-asserted-by":"crossref","unstructured":"Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, pp. 10\u2013pp. IEEE (2000)","DOI":"10.1109\/HICSS.2000.926982"},{"key":"426_CR14","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Kutylowski, M., Zatopianski, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 51\u201357 (2002)","DOI":"10.1145\/571825.571833"},{"key":"426_CR15","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Kutylowski, M., Zatopianski, J.: Energy-efficient size approximation of radio networks with no collision detection. In: Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON), pp. 279\u2013289 (2002)","DOI":"10.1007\/3-540-45655-4_31"},{"key":"426_CR16","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Kutylowski, M., Zatopianski, J.: Weak communication in radio networks. In: Proceedings of the 8th International European Conference on Parallel Computing (Euro-Par), pp. 965\u2013972 (2002)","DOI":"10.1007\/3-540-45706-2_137"},{"key":"426_CR17","doi-asserted-by":"crossref","unstructured":"Kardas, M., Klonowski, M., Pajak, D.: Energy-efficient leader election protocols for single-hop radio networks. In: Proceedings of the 42nd International Conference on Parallel Processing, pp. 399\u2013408 (2013)","DOI":"10.1109\/ICPP.2013.49"},{"issue":"4","key":"426_CR18","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen 77(4), 453\u2013465 (1916)","journal-title":"Mathematische Annalen"},{"key":"426_CR19","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 148\u2013157 (2005)","DOI":"10.1145\/1073814.1073842"},{"issue":"8","key":"426_CR20","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1109\/71.877942","volume":"11","author":"K Nakano","year":"2000","unstructured":"Nakano, K., Olariu, S.: Energy-efficient initialization protocols for single-hop radio networks with no collision detection. IEEE Trans. Parallel Distrib. Syst. 11(8), 851\u2013863 (2000)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"426_CR21","unstructured":"Polastre, J., Szewczyk, R., Culler, D.: Telos: enabling ultra-low power wireless research. In: Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks, pp. 364\u2013369. IEEE (2005)"},{"issue":"1","key":"426_CR22","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s10107-013-0731-3","volume":"147","author":"X Wang","year":"2014","unstructured":"Wang, X., Song, X., Yuan, J.: On matching cover of graphs. Math. Program. 147(1), 499\u2013518 (2014)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"426_CR23","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/S0304-3975(02)00653-9","volume":"297","author":"M Zito","year":"2003","unstructured":"Zito, M.: Small maximal matchings in random graphs. Theor. Comput. Sci. 297(1\u20133), 487\u2013507 (2003)","journal-title":"Theor. Comput. Sci."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00426-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00426-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00426-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T01:01:01Z","timestamp":1727139661000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00426-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,7]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["426"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00426-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,7]]},"assertion":[{"value":"17 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}