{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:51:26Z","timestamp":1725486686434},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","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":[[2000]]},"DOI":"10.1007\/3-540-44436-x_23","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T05:33:14Z","timestamp":1182144794000},"page":"226-237","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Inapproximability of Broadcasting Time"],"prefix":"10.1007","author":[{"given":"Christian","family":"Schindelhauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"BGNS98. A. Bar-Noy, S. Guha, J. Naor, B. Schieber, Multicasting in heterogeneous networks, In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 1998, 448\u2013453.","DOI":"10.1145\/276698.276857"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1137\/0405002","volume":"5","author":"BHLP92. J.-C. Bermond","year":"1992","unstructured":"BHLP92. J.-C. Bermond, P. Hell, A. Liestman, and J. Peters, Broadcasting in Bounded Degree Graphs, SIAM J. Disc. Math. 5, 1992, 10\u201324.","journal-title":"SIAM J. Disc. Math."},{"issue":"4","key":"23_CR3","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"Feig98. U. Feige","year":"1998","unstructured":"Feig98. U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, Vol. 45, 1998 (4):634\u2013652.","journal-title":"Journal of the ACM"},{"key":"23_CR4","unstructured":"GaJo79. M. Garey and D. Johnson, Computers and Intractability, A Guide To the Theory of NP-Completeness, Freeman 1979."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"H\u00e5ast97. J. H\u00e5astad, Some optimal inapproximability results, In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997, 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"HHL88. S. Hedetniemi","year":"1988","unstructured":"HHL88. S. Hedetniemi, S. Hedetniemi, and A. Liestman, A Survey of Gossiping and Broadcasting in Communication Networks, Networks 18, 1988, 319\u2013349.","journal-title":"Networks"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0166-218X(97)00110-8","volume":"83","author":"JRS98. A. Jakoby","year":"1998","unstructured":"JRS98. A. Jakoby, R. Reischuk, C. Schindelhauer, The Complexity of Broadcasting in Planar and Decomposable Graphs, Discrete Applied Mathematics 83, 1998, 179\u2013206.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/0401049","volume":"4","author":"LP88. A. Liestman","year":"1988","unstructured":"LP88. A. Liestman and J. Peters, Broadcast Networks of Bounded Degree, SIAM J. Disc. Math. 4, 1988, 531\u2013540.","journal-title":"SIAM J. Disc. Math."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(93)90066-I","volume":"46","author":"Midd93. M. Middendorf","year":"1993","unstructured":"Midd93. M. Middendorf, Minimum Broadcast Time is NP-complete for 3-regular planar graphs and deadline 2, Information Processing Letters, 46, 1993, 281\u2013287.","journal-title":"Information Processing Letters"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"MRSR95. M. V. Marathe, R. Ravi, R. Sundaram, S.S. Ravi, D.J. Rosenkrantz, H.B. Hunt III, Bicriteria network design problems, Proc. 22nd Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 944, Springer-Verlag, 1995, 487\u2013498.","DOI":"10.1007\/3-540-60084-1_99"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1137\/0210052","volume":"10","author":"SCH81. P. Slater","year":"1981","unstructured":"SCH81. P. Slater, E. Cockayne, and S. Hedetniemi, Information Dissemination in Trees, SIAM J. Comput. 10, 1981, 692\u2013701.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:38:19Z","timestamp":1558258699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_23"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"3 June 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}