{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T01:53:01Z","timestamp":1768873981936,"version":"3.49.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031433795","type":"print"},{"value":"9783031433801","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_24","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"334-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Complexity of\u00a0Broadcasting in\u00a0Graphs"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"issue":"2","key":"24_CR1","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":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-319-14974-5_3","volume-title":"Algorithms and Discrete Applied Mathematics","author":"P Bhabak","year":"2015","unstructured":"Bhabak, P., Harutyunyan, H.A.: Constant approximation for broadcasting in k-cycle graph. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 21\u201332. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-14974-5_3"},{"key":"24_CR3","doi-asserted-by":"publisher","unstructured":"Bhabak, P., Harutyunyan, H.A.: Approximation algorithm for the broadcast time in k-path graph. J. Interconnect. Netw. 19(4), 1950006:1\u20131950006:22 (2019). https:\/\/doi.org\/10.1142\/S0219265919500063","DOI":"10.1142\/S0219265919500063"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/s10878-015-9957-8","volume":"33","author":"M Cevnik","year":"2017","unstructured":"Cevnik, M., Zerovnik, J.: Broadcasting on cactus graphs. J. Comb. Optim. 33(1), 292\u2013316 (2017)","journal-title":"J. Comb. Optim."},{"issue":"40\u201342","key":"24_CR5","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"24_CR6","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1109\/71.706050","volume":"9","author":"J Cohen","year":"1998","unstructured":"Cohen, J., Fraigniaud, P., K\u00f6nig, J., Raspaud, A.: Optimized broadcasting and multicasting protocols in cut-through routed networks. IEEE Trans. Parallel Distrib. Syst. 9(8), 788\u2013802 (1998)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"24_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. 3rd edn. MIT Press, Cambridge (2009). https:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"24_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"24_CR9","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"issue":"4","key":"24_CR10","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":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230100106","volume":"10","author":"AM Farley","year":"1980","unstructured":"Farley, A.M.: Minimum-time line broadcast networks. Networks 10(1), 59\u201370 (1980)","journal-title":"Networks"},{"key":"24_CR12","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Fraigniaud, P., Golovach, P.A.: Parameterized complexity of broadcasting in graphs. CoRR abs\/2306.01536 (2023). https:\/\/doi.org\/10.48550\/arXiv.2306.01536","DOI":"10.48550\/arXiv.2306.01536"},{"key":"24_CR13","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. TTCSAES, Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/3-540-44676-1_37","volume-title":"Algorithms \u2014 ESA 2001","author":"P Fraigniaud","year":"2001","unstructured":"Fraigniaud, P.: Approximation algorithms for minimum-time broadcast under the vertex-disjoint paths mode. In: auf der Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 440\u2013451. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44676-1_37"},{"issue":"1\u20133","key":"24_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P Fraigniaud","year":"1994","unstructured":"Fraigniaud, P., Lazard, E.: Methods and problems of communication in usual networks. Discret. Appl. Math. 53(1\u20133), 79\u2013133 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"24_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Comb. 7(1), 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Comb."},{"key":"24_CR17","doi-asserted-by":"publisher","unstructured":"Gholami, M.S., Harutyunyan, H.A., Maraachlian, E.: Optimal broadcasting in fully connected trees. J. Interconnect. Netw. 23(1), 2150037:1\u20132150037:20 (2023). https:\/\/doi.org\/10.1142\/S0219265921500377","DOI":"10.1142\/S0219265921500377"},{"issue":"2","key":"24_CR18","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."},{"key":"24_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-031-30448-4_20","volume-title":"Algorithms and Complexity","author":"HA Harutyunyan","year":"2023","unstructured":"Harutyunyan, H.A., Hovhannisyan, N.: Broadcasting in split graphs. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, vol. 13898, pp. 278\u2013292. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30448-4_20"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10878-008-9160-2","volume":"16","author":"HA Harutyunyan","year":"2008","unstructured":"Harutyunyan, H.A., Maraachlian, E.: On broadcasting in unicyclic graphs. J. Comb. Optim. 16(3), 307\u2013322 (2008). https:\/\/doi.org\/10.1007\/s10878-008-9160-2","journal-title":"J. Comb. Optim."},{"issue":"4","key":"24_CR21","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"SM Hedetniemi","year":"1988","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319\u2013349 (1988). https:\/\/doi.org\/10.1002\/net.3230180406","journal-title":"Networks"},{"key":"24_CR22","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/b137871","volume-title":"Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance","author":"J Hromkovic","year":"2005","unstructured":"Hromkovic, J., Klasing, R., Pelc, A., Ruzicka, P., Unger, W.: Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/b137871"},{"issue":"9","key":"24_CR23","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1109\/12.29465","volume":"38","author":"SL Johnsson","year":"1989","unstructured":"Johnsson, S.L., Ho, C.: Optimum broadcasting and personalized communication in hypercubes. IEEE Trans. Comput. 38(9), 1249\u20131268 (1989)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"24_CR24","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987). https:\/\/doi.org\/10.1287\/moor.12.3.415","journal-title":"Math. Oper. Res."},{"issue":"3","key":"24_CR25","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":"4","key":"24_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983). https:\/\/doi.org\/10.1287\/moor.8.4.538","journal-title":"Math. Oper. Res."},{"issue":"2","key":"24_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285\u2013309 (1982). https:\/\/doi.org\/10.1145\/322307.322309","journal-title":"J. ACM"},{"issue":"5","key":"24_CR28","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). https:\/\/doi.org\/10.1109\/TC.1981.1675796","journal-title":"IEEE Trans. Comput."},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: 35th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 202\u2013213 (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"issue":"4","key":"24_CR30","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1137\/0210052","volume":"10","author":"PJ Slater","year":"1981","unstructured":"Slater, P.J., Cockayne, E.J., Hedetniemi, S.T.: Information dissemination in trees. SIAM J. Comput. 10(4), 692\u2013701 (1981). https:\/\/doi.org\/10.1137\/0210052","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR31","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0743-7315(90)90026-L","volume":"10","author":"QF Stout","year":"1990","unstructured":"Stout, Q.F., Wagar, B.: Intensive hypercube communication prearranged communication in link-bound machines. J. Parallel Distrib. Comput. 10(2), 167\u2013181 (1990)","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T20:11:56Z","timestamp":1730146316000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}