{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T22:56:53Z","timestamp":1787612213703,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662451731","type":"print"},{"value":"9783662451748","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_32","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T15:28:20Z","timestamp":1412004500000},"page":"469-483","source":"Crossref","is-referenced-by-count":6,"title":["Distributed Symmetry Breaking in Hypergraphs"],"prefix":"10.1007","author":[{"given":"Shay","family":"Kutten","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"32_CR1","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Series in Discrete Mathematics and Optimization. Wiley (2008), http:\/\/books.google.co.jp\/books?id=V8YgNioxF6AC"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.adhoc.2012.08.010","volume":"12","author":"C. Avin","year":"2014","unstructured":"Avin, C., Lando, Y., Lotker, Z.: Radio cover time in hyper-graphs. Ad Hoc Networks\u00a012, 278\u2013290 (2014)","journal-title":"Ad Hoc Networks"},{"key":"32_CR3","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. In: Frederickson, G.N. (ed.) SODA, pp. 203\u2013210. ACM\/SIAM (1992), http:\/\/dblp.uni-trier.de\/db\/conf\/soda\/soda92.html#AzarNR92"},{"issue":"6","key":"32_CR4","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1109\/JSAC.2004.830909","volume":"22","author":"H. Balakrishnan","year":"2004","unstructured":"Balakrishnan, H., Barrett, C.L., Kumar, V.S.A., Marathe, M.V., Thite, S.: The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications\u00a022(6), 1069\u20131079 (2004)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2013)","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"key":"32_CR6","unstructured":"Beame, P., Luby, M.: Parallel search for maximal independence given minimal dependence. In: SODA, pp. 212\u2013218 (1990)"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Bercea, I., Goyal, N., Harris, D., Srinivasan, A.: On computing maximal independent sets of hypergraphs in parallel. In: SPAA (June 2014)","DOI":"10.1145\/2612669.2612670"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Chen, Y.P., Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: MobiHoc, pp. 165\u2013172 (2002)","DOI":"10.1145\/513819.513821"},{"issue":"10","key":"32_CR9","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1109\/TC.1987.1676861","volume":"36","author":"I. Chlamtac","year":"1987","unstructured":"Chlamtac, I., Kutten, S.: Tree-based broadcasting in multihop radio networks. IEEE Trans. Computers\u00a036(10), 1209\u20131223 (1987)","journal-title":"IEEE Trans. Computers"},{"issue":"10","key":"32_CR10","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1109\/TPDS.2004.48","volume":"15","author":"F. Dai","year":"2004","unstructured":"Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst.\u00a015(10), 908\u2013920 (2004), http:\/\/dx.doi.org\/10.1109\/TPDS.2004.48","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: ICC (1), pp. 376\u2013380 (1997)","DOI":"10.1109\/ICC.1997.605303"},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.jcss.2005.04.002","volume":"71","author":"D.P. Dubhashi","year":"2005","unstructured":"Dubhashi, D.P., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci.\u00a071(4), 467\u2013479 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1109\/26.52656","volume":"38","author":"A. Ephremides","year":"1990","unstructured":"Ephremides, A., Truong, T.V.: Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications\u00a038(4), 456\u2013460 (1990)","journal-title":"IEEE Transactions on Communications"},{"issue":"1","key":"32_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J.A. Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput.\u00a027(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"key":"32_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-662-43951-7_41","volume-title":"Automata, Languages, and Programming","author":"M. Ghaffari","year":"2014","unstructured":"Ghaffari, M.: Near-optimal distributed approximation of minimum-weight connected dominating set. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol.\u00a08573, pp. 483\u2013494. Springer, Heidelberg (2014)"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/978-3-642-39212-2_51","volume-title":"Automata, Languages, and Programming","author":"D.G. Harris","year":"2013","unstructured":"Harris, D.G., Morsy, E., Pandurangan, G., Robinson, P., Srinivasan, A.: Efficient computation of balanced structures. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol.\u00a07966, pp. 581\u2013593. Springer, Heidelberg (2013)"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Ramachandran, V.: Parallel algorithms for shared-memory machines. In: Handbook of Theoretical Computer Science, vol.\u00a0A, pp. 869\u2013942 (1990)","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: The complexity of parallel search. J. Comput. Syst. Sci.\u00a036(2), 225\u2013253 (1988), announced at STOC 1985 and FOCS 1985","DOI":"10.1016\/0022-0000(88)90027-X"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Kelsen, P.: On the parallel complexity of computing a maximal independent set in a hypergraph. In: STOC, pp. 339\u2013350 (1992)","DOI":"10.1145\/129712.129745"},{"key":"32_CR20","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds. CoRR abs\/1011.5470 (2010)"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. In: PODC, pp. 100\u2013109 (2013)","DOI":"10.1145\/2484239.2484274"},{"issue":"1","key":"32_CR22","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms\u00a028(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"issue":"1","key":"32_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"32_CR24","unstructured":"Linial, N.: Dijkstra award talk Jerusalem (2013), http:\/\/www.cs.huji.ac.il\/~nati\/PAPERS\/disc_2013.pdf"},{"issue":"4","key":"32_CR25","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N. Linial","year":"1993","unstructured":"Linial, N., Saks, M.E.: Low diameter graph decompositions. Combinatorica\u00a013(4), 441\u2013454 (1993)","journal-title":"Combinatorica"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput.\u00a015(4), 1036\u20131053 (1986), announced at STOC 1985","DOI":"10.1137\/0215074"},{"issue":"2","key":"32_CR27","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1006\/jagm.1997.0884","volume":"25","author":"T. Luczak","year":"1997","unstructured":"Luczak, T., Szymanska, E.: A parallel randomized algorithm for finding a maximal independent set in a linear hypergraph. J. Algorithms\u00a025(2), 311\u2013320 (1997)","journal-title":"J. Algorithms"},{"key":"32_CR28","doi-asserted-by":"crossref","unstructured":"Makino, K., Kameda, T.: Efficient generation of all regular non-dominated coteries. In: PODC, pp. 279\u2013288 (2000)","DOI":"10.1145\/343477.343629"},{"issue":"5-6","key":"32_CR29","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00446-010-0121-5","volume":"23","author":"Y. M\u00e9tivier","year":"2011","unstructured":"M\u00e9tivier, Y., Robson, J.M., Saheb-Djahromi, N., Zemmari, A.: An optimal bit complexity randomized distributed mis algorithm. Distributed Computing\u00a023(5-6), 331\u2013340 (2011)","journal-title":"Distributed Computing"},{"key":"32_CR30","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. SIAM, Philadelphia (2000)"},{"issue":"5","key":"32_CR31","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A.D. Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput.\u00a041(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"32_CR32","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/jagm.1996.0832","volume":"23","author":"R. Thurimella","year":"1997","unstructured":"Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components. J. Algorithms\u00a023(1), 160\u2013179 (1997)","journal-title":"J. Algorithms"},{"key":"32_CR33","doi-asserted-by":"crossref","unstructured":"Wasserman, S., Faust, K.: Social network analysis: Methods and Applications. Cambridge University Press (1994)","DOI":"10.1017\/CBO9780511815478"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:11:37Z","timestamp":1746396697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}