{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:16:43Z","timestamp":1751516203106,"version":"3.41.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_45","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"611-624","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Plane Gossip: Approximating Rumor Spread in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Jennifer","family":"Iglesias","sequence":"first","affiliation":[]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7603-1207","authenticated-orcid":false,"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Ravi","family":"Sundaram","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: PODC, pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","volume":"43","author":"N Alon","year":"1991","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 290\u2013298 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"45_CR3","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(72)90001-5","volume":"2","author":"B Baker","year":"1972","unstructured":"Baker, B., Shostak, R.: Gossips and telephones. Discret. Math. 2(3), 191\u2013193 (1972)","journal-title":"Discret. Math."},{"issue":"2","key":"45_CR4","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/S0097539798347906","volume":"30","author":"A Bar-Noy","year":"2000","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Message multicasting in heterogeneous networks. SIAM J. Comput. 30(2), 347\u2013358 (2000)","journal-title":"SIAM J. Comput."},{"key":"45_CR5","unstructured":"Cherkassky, B.: Mnogopolyusnye dvukhproduktovye zadachi [Russian: Multiterminal two commodity problems]. Issledovaniya po Diskretnoi Optimizatsii [Russian: Studies in discrete optimization], pp. 261\u2013289 (1976)"},{"issue":"3","key":"45_CR6","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1137\/S0097539704440740","volume":"35","author":"M Elkin","year":"2005","unstructured":"Elkin, M., Kortsarz, G.: A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. SIAM J. Comput. 35(3), 672\u2013689 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"45_CR7","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1137\/S0895480104445319","volume":"19","author":"M Elkin","year":"2005","unstructured":"Elkin, M., Kortsarz, G.: Polylogarithmic additive inapproximability of the radio broadcast problem. SIAM J. Discret. Math. 19(4), 881\u2013899 (2005)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"45_CR8","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00453-005-1196-4","volume":"45","author":"M Elkin","year":"2006","unstructured":"Elkin, M., Kortsarz, G.: An approximation algorithm for the directed telephone multicast problem. Algorithmica 45(4), 569\u2013583 (2006)","journal-title":"Algorithmica"},{"issue":"4","key":"45_CR9","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.jcss.2005.12.002","volume":"72","author":"M Elkin","year":"2006","unstructured":"Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4), 648\u2013659 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"45_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447\u2013460 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"45_CR11","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: SODA 2012, pp. 1642\u20131660. SIAM (2012)","DOI":"10.1137\/1.9781611973099.130"},{"key":"45_CR12","series-title":"Oxford Lecture Series in Mathematics and Its Applications.","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, Oxford (2011)"},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-11476-2_2","volume-title":"Structural Information and Communication Complexity","author":"L G\u0105sieniec","year":"2010","unstructured":"G\u0105sieniec, L.: On efficient gossiping in radio networks. In: Kutten, S., \u017derovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 2\u201314. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11476-2_2"},{"issue":"4","key":"45_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00446-006-0011-z","volume":"19","author":"L Gasieniec","year":"2007","unstructured":"Gasieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. Distrib. Comput. 19(4), 289\u2013300 (2007)","journal-title":"Distrib. Comput."},{"key":"45_CR15","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: STACS 2011, vol. 9, pp. 57\u201368 (2011)"},{"issue":"2","key":"45_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/0404021","volume":"4","author":"M Grigni","year":"1991","unstructured":"Grigni, M., Peleg, D.: Tight bounds on minimum broadcast networks. SIAM J. Discret. Math. 4(2), 207\u2013222 (1991)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"45_CR17","doi-asserted-by":"publisher","first-page":"447","DOI":"10.4153\/CMB-1972-081-0","volume":"15","author":"A Hajnal","year":"1972","unstructured":"Hajnal, A., Milner, E.C., Szemer\u00e9di, E.: A cure for the telephone disease. Canad. Math. Bull 15(3), 447\u2013450 (1972)","journal-title":"Canad. Math. Bull"},{"key":"45_CR18","unstructured":"Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R.: Rumors across radio, wireless, telephone. In: FSTTCS, pp. 517\u2013528 (2015)"},{"key":"45_CR19","unstructured":"Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R.: Plane gossip: Approximating rumor spread in planar graphs. CoRR, abs\/1612.01492 (2016)"},{"key":"45_CR20","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: FOCS 2000, Washington, DC, USA, pp. 565\u2013574. IEEE (2000)"},{"issue":"1","key":"45_CR21","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01840353","volume":"2","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2(1), 113\u2013129 (1987)","journal-title":"Algorithmica"},{"issue":"3","key":"45_CR22","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0895480193245923","volume":"8","author":"G Kortsarz","year":"1995","unstructured":"Kortsarz, G., Peleg, D.: Approximation algorithms for minimum-time broadcast. SIAM J. Discret. Math. 8(3), 401\u2013427 (1995)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"45_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00446-006-0007-8","volume":"19","author":"DR Kowalski","year":"2007","unstructured":"Kowalski, D.R., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), 185\u2013195 (2007)","journal-title":"Distrib. Comput."},{"issue":"2","key":"45_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"45_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L Lov\u00e1sz","year":"1976","unstructured":"Lov\u00e1sz, L.: On some connectivity properties of Eulerian graphs. Acta Math. Acad. Sci. Hung. 28, 129\u2013138 (1976)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"45_CR26","doi-asserted-by":"crossref","unstructured":"Manne, F., Wang, S., Xin, Q.: Faster radio broadcast in planar graphs. In: WONS, pp. 9\u201313 (2008)","DOI":"10.4304\/jnw.3.2.9-16"},{"key":"45_CR27","series-title":"Cambridge International Series on Parallel Computation","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge International Series on Parallel Computation. Cambridge University Press, Cambridge (1995)"},{"key":"45_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-662-43951-7_48","volume-title":"Automata, Languages, and Programming","author":"A Nikzad","year":"2014","unstructured":"Nikzad, A., Ravi, R.: Sending secrets swiftly: approximation algorithms for generalized multicast problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 568\u2013607. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_48"},{"issue":"5","key":"45_CR29","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TC.1981.1675796","volume":"30","author":"A Proskurowski","year":"1981","unstructured":"Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput. 30(5), 363\u2013366 (1981)","journal-title":"IEEE Trans. Comput."},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: FOCS, pp. 202\u2013213. IEEE (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"key":"45_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11682462_4","volume-title":"LATIN 2006: Theoretical Informatics","author":"R Ravi","year":"2006","unstructured":"Ravi, R.: Matching based augmentations for approximating connectivity problems. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 13\u201324. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11682462_4"},{"issue":"6","key":"45_CR32","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"issue":"19","key":"45_CR33","first-page":"188","volume":"3","author":"R Tijdeman","year":"1971","unstructured":"Tijdeman, R.: On a telephone problem. Nieuw Archief voor Wiskunde 3(19), 188\u2013192 (1971)","journal-title":"Nieuw Archief voor Wiskunde"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:30:12Z","timestamp":1751481012000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}