{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:01:35Z","timestamp":1725487295016},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_19","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"212-223","source":"Crossref","is-referenced-by-count":10,"title":["Approximation Algorithm for Directed Telephone Multicast Problem"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"19_CR1","unstructured":"N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"A. Bar-noy, S. Guha, J. Naor and B. Schieber. Multicasting in Heterogeneous Networks, In Proc. of 30th ACM Annual Symp. on Theory of Computing 1998.","DOI":"10.1145\/276698.276857"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF01184933","volume":"27","author":"A. Bar-Noy","year":"1994","unstructured":"A. Bar-Noy and S. Kipnis, \u201cDesigning Broadcasting Algorithms in the Postal Model for Message-Passing Systems,\u201d Mathematical System Theory, Vol. 27, pp. 431\u2013452, 1994.","journal-title":"Mathematical System Theory"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, A measure of asymptotic efficiency for tests of an hypothesis based on the sum of observations, Annals of Mathematical Statistics, 23:493\u2013509, 1952.","journal-title":"Annals of Mathematical Statistics"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"M. Elkin and G. Kortsarz, A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem, In Proc. of 34th ACM Annual Symp. on Theory of Computing, pp. 438\u2013447, 2002.","DOI":"10.1145\/509907.509972"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"M. Elkin and G. Kortsarz, A sublogarithmic approximation algorithm for the undirected telephone broadcast problem: a path out of a jungle. In Proc. of 14th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 76\u201385, 2003.","DOI":"10.1145\/509907.509972"},{"key":"19_CR7","first-page":"440","volume":"2161","author":"P. Fraigniaud","year":"2001","unstructured":"P. Fraigniaud Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode, In 9th Annual European Symposium. on Algorithms (ESA\u2019 01), LNCS Vol. 2161, pp. 440\u2013451, 2001.","journal-title":"9th Annual European Symposium. on Algorithms (ESA\u2019 01)"},{"key":"19_CR8","unstructured":"M. Furer and B. Raghavachari. An NC approximation algorithm for the minimum degree spanning tree problem. In Proc. of the 28th Annual Allerton Conf. on Communication, Control and Computing, pp. 274\u2013281, 1990."},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S. Hedetniemi","year":"1988","unstructured":"S. Hedetniemi, S. Hedetniemi, and A. Liestman. A survey of broadcasting and gossiping in communication networks. Networks, 18: 319\u2013349, 1988.","journal-title":"Networks"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"H. B. Hunt","year":"1998","unstructured":"H. B. Hunt, M. V. Marathe, R. Sundaram, R. Ravi, S. S. Ravi and D. J. Rosenkrantz. Bicriteria network design problems, Journal of Algorithms, Vol. 28, No. 1, 142\u2013171 (1998).","journal-title":"Journal of Algorithms"},{"key":"19_CR11","unstructured":"L. G. Khachiyan. A Polynomial Algorithm in Linear Programming, Doklady Akademii Nauk SSSR 244, pp. 1093\u20131096, 1979."},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, vol. 4(1984), pp. 373\u2013396.","journal-title":"Combinatorica"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0895480193245923","volume":"8","author":"G. Kortsarz","year":"1995","unstructured":"G. Kortsarz and D. Peleg. Approximation algorithms for minimum time broadcast, SIAM journal on discrete methods, vol. 8, pp. 401\u2013427, 1995.","journal-title":"SIAM journal on discrete methods"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"L. K. Lenstra","year":"1990","unstructured":"L. K. Lenstra and D. Shmoys and E. Tardos, \u201cApproximation algorithms for scheduling unrelated parallel machines\u201d, Math. Programming, 46, 259\u2013271. (1990).","journal-title":"Math. Programming"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"R. Krishnan and B. Raghavachari. The Directed Minimum-Degree Spanning Tree Problem. FSTTCS 2001, 232\u2013243.","DOI":"10.1007\/3-540-45294-X_20"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(93)90066-I","volume":"46","author":"M. Middendorf","year":"1993","unstructured":"M. Middendorf. Minimum Broadcast Time is NP-complete for 3-regular planar graphs and deadline 2. Inf. Process. Lett. 46 (1993) 281\u2013287.","journal-title":"Inf. Process. Lett."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S. A. Plotkin","year":"1995","unstructured":"S. A. Plotkin and D. B. Shmoys and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20, 1995, 257\u2013301.","journal-title":"Mathematics of Operations Research"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of computer and system sciences, 37:130\u2013143,1988.","journal-title":"Journal of computer and system sciences"},{"key":"19_CR20","unstructured":"R. Ravi, Rapid rumor ramification: Approximating the minimum broadcast time. In Proc. of the IEEE Symp. on Foundations of Computer Science (FOCS\u2019 94), pp. 202\u2013213, 1994."},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"R. Raz, S. Safra. A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP, in Proc. of the 29th Symp. on Theory of Comp., pp. 475\u2013484, 1997.","DOI":"10.1145\/258533.258641"},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. Thompson, Randomized Rounding, Combinatorica, vol. 7, pp. 365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"C. Schindelhauer, On the Inapproximability of Broadcasting Time, In The 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201900), 2000.","DOI":"10.1007\/3-540-44436-X_23"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T10:28:31Z","timestamp":1683973711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":23,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-45061-0_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}