{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T13:27:35Z","timestamp":1772458055238,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_48","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T04:37:49Z","timestamp":1402461469000},"page":"568-607","source":"Crossref","is-referenced-by-count":3,"title":["Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems"],"prefix":"10.1007","author":[{"given":"Afshin","family":"Nikzad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"2934","DOI":"10.1109\/26.328973","volume":"42","author":"B. Awerbuch","year":"1994","unstructured":"Awerbuch, B., Kutten, S., Peleg, D.: On buffer-economical store-and-forward deadlock prevention. IEEE Transactions on Communication\u00a042, 2934\u20132937 (1994)","journal-title":"IEEE Transactions on Communication"},{"key":"48_CR2","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. Discrete Math\u00a02, 191\u2013193 (1972)","journal-title":"Discrete Math"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Haeupler, B., Kelner, J., Maymounkov, P.: Global Computation in a Poorly Connected World: Fast Rumor Spreading No Dependence on Conductance. In: STOC: ACM Symposium on Theory of Computing (2012)","DOI":"10.1145\/2213977.2214064"},{"issue":"5","key":"48_CR4","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1006\/eujc.1999.0388","volume":"21","author":"T. Dvork","year":"2000","unstructured":"Dvork, T.: Chromatic Index of Hypergraphs and Shannons Theorem. European Journal of Combinatorics\u00a021(5), 585\u2013591 (2000)","journal-title":"European Journal of Combinatorics"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"Elkin, M., Kortsarz, M.G.: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC 2002 (2002)","DOI":"10.1145\/509967.509972"},{"issue":"4","key":"48_CR6","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\u00a045(4), 569\u2013583 (2006)","journal-title":"Algorithmica"},{"key":"48_CR7","unstructured":"Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast. In: SODA 2003 Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 76\u201385 (2003)"},{"key":"48_CR8","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. System Sci.\u00a057, 187\u2013199 (1998)","journal-title":"J. Comput. System Sci."},{"key":"48_CR9","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. Discrete Math.\u00a04, 207\u2013222 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"48_CR10","doi-asserted-by":"crossref","unstructured":"Guha, S., Bar-noy, A., Naor, J., Schieber, B.: Multicasting in heterogeneous networks. In: STOC 1998 Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 448\u2013453 (1998)","DOI":"10.1145\/276698.276857"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. In: SODA 2011 Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1615\u20131626 (2011)","DOI":"10.1137\/1.9781611973082.125"},{"key":"48_CR12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.4153\/CMB-1972-081-0","volume":"15","author":"A. Hajnal","year":"1976","unstructured":"Hajnal, A., Milner, E.C., Szemeredi, E.: A cure for the telephone disease. Canad Math. Bull\u00a015, 447\u2013450 (1976)","journal-title":"Canad Math. Bull"},{"key":"48_CR13","doi-asserted-by":"crossref","unstructured":"Haeupler, B.: Simple, Fast, and Deterministic Gossip and Rumor Spreading. In: SODA: ACM-SIAM Symposium on Discrete Algorithms (2013)","DOI":"10.1137\/1.9781611973105.51"},{"key":"48_CR14","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 Journal on Discrete Methods\u00a08, 401\u2013427 (1995)","journal-title":"SIAM Journal on Discrete Methods"},{"key":"48_CR15","doi-asserted-by":"crossref","unstructured":"Kossinets, G., Kleinberg, J., Watts, D.: The structure of information pathways in a social communication network. In: Proceedings of the 14th SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 435\u2013443 (2008)","DOI":"10.1145\/1401890.1401945"},{"key":"48_CR16","unstructured":"Leighton, F.T., Lewin, D.M.: Global Hosting System, US Patent 6108703 (Issued August 22, 2000)"},{"key":"48_CR17","doi-asserted-by":"crossref","unstructured":"Onus, M., Richa, A.W.: Minimum maximum-degree publish-subscribe overlay network design. IEEE\/ACM Transactions on Networking, TON (2011)","DOI":"10.1109\/TNET.2011.2144999"},{"key":"48_CR18","doi-asserted-by":"crossref","unstructured":"Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput.\u00a0C-30, 363 (1981)","DOI":"10.1109\/TC.1981.1675796"},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. In: 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pp. 10\u201318 (1986)","DOI":"10.1109\/SFCS.1986.45"},{"key":"48_CR20","unstructured":"Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: 35th Annual Symposium on Foundations of Computer Science, FOCS 1994 (1994)"},{"issue":"9","key":"48_CR21","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1109\/TC.1984.1676496","volume":"33","author":"P. Scheuermann","year":"1984","unstructured":"Scheuermann, P., Wu, G.: Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks. IEEE Transactions on Computers\u00a033(9), 804\u2013811 (1984)","journal-title":"IEEE Transactions on Computers"},{"key":"48_CR22","unstructured":"Schrijver, A.: Combinatorial optimization: Polyhedra and Eficiency, ch. 21. Springer (2003)"},{"key":"48_CR23","first-page":"188","volume":"19","author":"R. Tijdeman","year":"1971","unstructured":"Tijdeman, R.: On a Telephone Problem. Nieuw Arch. Wisk.\u00a019, 188\u2013192 (1971)","journal-title":"Nieuw Arch. Wisk."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:19:27Z","timestamp":1558909167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}