{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:02:25Z","timestamp":1742634145453},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_37","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T16:43:15Z","timestamp":1179506595000},"page":"440-451","source":"Crossref","is-referenced-by-count":9,"title":["Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Multicasting in heterogeneous networks. In 30th ACM Symposium on Theory of Computing (STOC\u2019 98), pages 448\u2013453, 1998.","DOI":"10.1145\/276698.276857"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"D. Barth and P. Fraigniaud. Approximation algorithms for structured communication problems. In 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA\u2019 97),pages 180\u2013188, 1997. (Tech. Rep. LRI-1239, Univ. Paris-Sud. http:\/\/www.lri.fr\/~pierre ).","DOI":"10.1145\/258492.258510"},{"key":"37_CR3","unstructured":"J.-C. Bermond, A. Bonnecaze, T. Kodate, S. P\u00e9rennes, and P. Sole. Broadcasting in hypercubes under the circuit-switched model. In IEEE Int. Parallel and Distributed Processing Symp. (IPDPS), 2000."},{"key":"37_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/3-540-60084-1_69","volume-title":"22nd International Colloquium on Automata, Languages and Programming (ICALP\u201995)","author":"J.-C. Bermond","year":"1995","unstructured":"J.-C. Bermond, L. Gargano, A. Rescigno, and U. Vaccaro. Fast gossiping by short messages. In 22nd International Colloquium on Automata, Languages and Programming (ICALP\u201995), volume 944 of Lecture Notes in Computer Science, pages 135\u2013146, 1995."},{"key":"37_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/3-540-60618-1_79","volume-title":"21st Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201995)","author":"B. Birchler","year":"1995","unstructured":"B. Birchler, A.-H. Esfahanian, and E. Torng. Toward a general theory of unicast-based multicast communication. In 21st Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201995), volume 1017 of LNCS, pages 237\u2013251, 1995."},{"key":"37_CR6","unstructured":"B. Birchler, A.-H. Esfahanian, and E. Torng. Information dissemination in restricted routing networks. In International Symposium on Combinatorics and Applications, pages 33\u201344, 1996."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"J. Cohen. Broadcasting, multicasting and gossiping in trees under the all-port line model. In 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201998), pages 164\u2013171, 1998.","DOI":"10.1145\/277651.277682"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"J. Cohen, P. Fraigniaud, J.-C. Konig, and A. Raspaud. Broadcasting and multicasting in cut-through routed networks. In 11th IEEE Int. Parallel Processing Symposium (IPPS\u201997), pages 734\u2013738, 1997.","DOI":"10.1109\/IPPS.1997.580989"},{"key":"37_CR9","unstructured":"J. Cohen, P. Fraigniaud, and M. Mitjana. Scheduling calls for multicasting in tree-networks. In 10th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201999), pages 881\u2013882, 1999."},{"issue":"3","key":"37_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1109\/49.564128","volume":"15","author":"C. Diot","year":"1997","unstructured":"C. Diot, W. Dabbous, and J. Crowcroft. Multipoint communication: a survey of protocols,functions, and mechanisms. IEEE Journal on Selected Areas in Communications, 15(3):277\u2013290, 1997.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230100106","volume":"10","author":"A. Farley","year":"1980","unstructured":"A. Farley. Minimum-time line broadcast networks. Networks, 10:59\u201370, 1980.","journal-title":"Networks"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige. A threshold of lnn for approximating set cover. Journal of the ACM, 45:634\u2013652, 1998.","journal-title":"Journal of the ACM"},{"key":"37_CR13","unstructured":"P. Fraigniaud. Minimum-time broadcast under the edge-disjoint paths mode. In 2nd Int. Conference on Fun with Algorithms (FUN\u201901), Carleton Scientific, 2001."},{"key":"37_CR14","volume-title":"Tech. Rep. LRI-1264","author":"P. Fraigniaud","year":"2000","unstructured":"P. Fraigniaud. Approximation algorithms for collective communications with limited link and node-contention. Tech. Rep. LRI-1264, Universit\u00e9 Paris-Sud, France, 2000."},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P. Fraigniaud","year":"1994","unstructured":"P. Fraigniaud and E. Lazard. Methods and Problems of Communication in Usual Networks. Discrete Applied Mathematics, 53:79\u2013133, 1994.","journal-title":"Discrete Applied Mathematics"},{"key":"37_CR16","unstructured":"M. F\u00fcrer and B. Raghavachari. Approximating the minimum degree spanning tree within one from the optimal degree. In 3rd Annual ACM-SIAM Sumposium on Discrete Algorithms (SODA\u201992), pages 317\u2013324, 1992."},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"M. F\u00fcrer and B. Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17:409\u2013423, 1994.","journal-title":"Journal of Algorithms"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S. Hedetniemi","year":"1986","unstructured":"S. Hedetniemi, S. Hedetniemi, and A. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 18:319\u2013349, 1986.","journal-title":"Networks"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u0107, R. Klasing, B. Monien, and R. Peine. Dissemination of information in interconnection networks (broadcasting and gossiping). In Ding-Zhu Du and D. Frank Hsu, editors, Combinatorial Network Theory, pages 125\u2013212. Kluwer Academic, 1995.","DOI":"10.1007\/978-1-4757-2491-2_5"},{"issue":"4","key":"37_CR20","first-page":"295","volume":"15","author":"J. Hromkovi\u0107","year":"1996","unstructured":"J. Hromkovi\u0107, R. Klasing, and E. Stohr. Dissemination of information in vertex-disjoint paths mode. Computer and Artificial Intelligence, 15(4):295\u2013318, 1996.","journal-title":"Computer and Artificial Intelligence"},{"key":"37_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/inco.1995.1154","volume":"1231","author":"J. Hromkovi\u0107","year":"1995","unstructured":"J. Hromkovi\u0107, R. Klasing, E. Stohr, and Wagener H. Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs. Information and Computation, 123(1):17\u201328, 1995.","journal-title":"Information and Computation"},{"issue":"1","key":"37_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.2618","volume":"133","author":"J. Hromkovi\u0107","year":"1997","unstructured":"J. Hromkovi\u0107, R. Klasing, W. Unger, and H. Wagener. Optimal algorithms for broadcast and gossip in the edge-disjoint paths mode. Information and Computation, 133(1):1\u201333, 1997.","journal-title":"Information and Computation"},{"issue":"1-3","key":"37_CR23","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0166-218X(97)00112-1","volume":"83","author":"R. Klasing","year":"1998","unstructured":"R. Klasing. The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex-bisection width. Discrete Applied Maths, 83(1-3):229\u2013246, 1998.","journal-title":"Discrete Applied Maths"},{"issue":"3","key":"37_CR24","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 Mathematics, 8(3):401\u2013427, 1995.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"37_CR25","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1016\/S0140-3664(97)00153-9","volume":"20","author":"W. Mostafa","year":"1998","unstructured":"W. Mostafa and M. Singhal. A taxonomy of multicast protocols for internet applications. Computer Communications, 20:1448\u20131457, 1998.","journal-title":"Computer Communications"},{"issue":"3","key":"37_CR26","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1109\/71.491578","volume":"7","author":"J. Peters","year":"1996","unstructured":"J. Peters and M. Syska. Circuit-switched broadcasting in torus networks. IEEE Transactions on Parallel and Distributed Systems, 7(3):246\u2013255, 1996.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"37_CR27","doi-asserted-by":"crossref","unstructured":"R. Ravi. Rapid rumor ramification: approximating the minimum broadcast time. In 35-th IEEE Symposium on Foundations of Computer Science, pages 202\u2013213, 1994.","DOI":"10.1109\/SFCS.1994.365693"},{"key":"37_CR28","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_23","volume-title":"3rd Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"C. Schindelhauer","year":"2000","unstructured":"C. Schindelhauer. On the inapproximability of broadcasting time. In 3rd Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), LNCS 1913. Springer-Verlag, 2000."},{"key":"37_CR29","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0166-218X(94)90007-8","volume":"55","author":"H. Yinnone","year":"1994","unstructured":"H. Yinnone. Maximum number of disjoint paths connecting specified terminals in a graph. Disc. Appl. Maths. 55:183\u2013195, 1994.","journal-title":"Disc. Appl. Maths."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T04:44:08Z","timestamp":1556426648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}