{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:12Z","timestamp":1750306392746,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,9]],"date-time":"2015-03-09T00:00:00Z","timestamp":1425859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,3,9]]},"abstract":"<jats:p>For many distributed computing problems there exists a characterizing combinatorial structure. In other words, the existence of an algorithm for solving the problem on any graph G in time T(G) implies the existence of the structure in G with some parameter related to T(G), and vice versa. Such relations go back to classic examples, such as synchronizers and sparse spanners, and continue to emerge in recent studies of gossip algorithms and multicast algorithms in different communication settings. In this article, we give an overview of both old and recent results that illustrate these connections. We discuss how finding distributed algorithms as well as proving lower bounds can be reduced to studying combinatorial graph structures.<\/jats:p>","DOI":"10.1145\/2744447.2744461","type":"journal-article","created":{"date-parts":[[2015,3,12]],"date-time":"2015-03-12T12:18:05Z","timestamp":1426162685000},"page":"63-76","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Algorithms as Combinatorial Structures"],"prefix":"10.1145","volume":"46","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2015,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.1.104"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400757"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2534493"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611491"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634115"},{"key":"e_1_2_1_7_1","unstructured":"Keren Censor-Hillel and George Giakkoupis. Fast and robust information spreading. Unpublished manuscript.  Keren Censor-Hillel and George Giakkoupis. Fast and robust information spreading. Unpublished manuscript."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214064"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133071"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027274"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993640"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_27"},{"key":"e_1_2_1_15_1","first-page":"773","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Doerr Benjamin","year":"2008"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_31"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958171.1958186"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095246"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810505"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62252"},{"key":"e_1_2_1_22_1","first-page":"115","volume-title":"Theory of Graphs (Proceedings of the Colloquium in Tihany 1966","author":"Gallai Tibor","year":"1968"},{"key":"e_1_2_1_23_1","first-page":"57","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Giakkoupis George","year":"2011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095245"},{"key":"e_1_2_1_25_1","first-page":"314","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Giakkoupis George","year":"2012"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133072"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993676"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627868"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19650280503"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380796"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652161"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90087-2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146401"},{"key":"e_1_2_1_38_1","first-page":"445","article-title":"John Alvah Nash-Williams. Edge-disjoint spanning trees of finite graphs","volume":"36","author":"St Crispin","year":"1961","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"David Peleg and Alejandro A. Sch\u00e4ffer. Graph spanners. Journal of graph theory 13(1):99--116 1989.  David Peleg and Alejandro A. Sch\u00e4ffer. Graph spanners. Journal of graph theory 13(1):99--116 1989.","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_2_1_43_1","first-page":"129","article-title":"Nombre chromatique et plus longs chemins d'un graphe","volume":"1","author":"Roy Bernard","year":"1967","journal-title":"Rev. Fran\u00e7aise Informat. Recherche Op\u00e8rationnelle"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133073"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231858"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"e_1_2_1_47_1","unstructured":"L.M. Vitaver. Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix. Dokl. Akad. Nauk. SSSR147 pages 758--759 1962. In Russian.  L.M. Vitaver. Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix. Dokl. Akad. Nauk. SSSR147 pages 758--759 1962. In Russian."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2744447.2744461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2744447.2744461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:16Z","timestamp":1750223236000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2744447.2744461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,9]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,9]]}},"alternative-id":["10.1145\/2744447.2744461"],"URL":"https:\/\/doi.org\/10.1145\/2744447.2744461","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2015,3,9]]},"assertion":[{"value":"2015-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}