{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T02:30:41Z","timestamp":1747881041078,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"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-30448-4_20","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"278-292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Broadcasting in\u00a0Split Graphs"],"prefix":"10.1007","author":[{"given":"Hovhannes A.","family":"Harutyunyan","sequence":"first","affiliation":[]},{"given":"Narek","family":"Hovhannisyan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1504\/IJNS.2016.073557","volume":"1","author":"I Belik","year":"2016","unstructured":"Belik, I.: The analysis of split graphs in social networks based on the k-cardinality assignment problem. Int. J. Netw. Sci. 1(1), 53\u201362 (2016)","journal-title":"Int. J. Netw. Sci."},{"issue":"4","key":"20_CR2","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-020-09967-8","volume":"65","author":"R Belmonte","year":"2021","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. Theory Comput. Syst. 65(4), 662\u2013686 (2021)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1017\/S1446788700023077","volume":"38","author":"EA Bender","year":"1985","unstructured":"Bender, E.A., Richmond, L.B., Wormald, N.C.: Almost all chordal graphs split. J. Aust. Math. Soc. 38(2), 214\u2013221 (1985)","journal-title":"J. Aust. Math. Soc."},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Bhabak, P., Harutyunyan, H.A., Kropf, P.: Efficient broadcasting algorithm in Harary-like networks. In: 46th International Conference on Parallel Processing Workshops (ICPPW 2017), pp. 162\u2013170. IEEE (2017)","DOI":"10.1109\/ICPPW.2017.34"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Bhabak, P., Harutyunyan, H.A., Tanna, S.: Broadcasting in Harary-like graphs. In: 17th International Conference on Computational Science and Engineering (CSE 2014), pp. 1269\u20131276. IEEE (2014)","DOI":"10.1109\/CSE.2014.244"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/3-540-46541-3_33","volume-title":"STACS 2000","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: $$\\lambda $$-coloring of graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 395\u2013406. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46541-3_33"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Collins, K.L., Trenk, A.N.: Finding balance: split graphs and related classes. arXiv preprint arXiv:1706.03092 (2017)","DOI":"10.37236\/7091"},{"key":"20_CR9","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. In: Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (SECCGTC 1977), vol. XIX, pp. 311\u2013315. Winnipeg: Utilitas Math (1977)"},{"key":"20_CR10","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in networks. In: Flows in Networks. Princeton University Press (2015)"},{"issue":"1\u20133","key":"20_CR11","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."},{"key":"20_CR12","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Gholami, S., Harutyunyan, H.A., Maraachlian, E.: Optimal broadcasting in fully connected trees. J. Interconnect. Netw. 23(01), 2150037:1\u20132150037:20 (2023)","DOI":"10.1142\/S0219265921500377"},{"key":"20_CR14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, Amsterdam (2004)"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Harutyunyan, H.A., Hovhannisyan, N., Maraachlian, E.: Broadcasting in chains of rings. In: Submitted to International Workshop on Combinatorial Algorithms (IWOCA 2023) (2023)","DOI":"10.1109\/ICUFN57995.2023.10201234"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Harutyunyan, H.A., Liestman, A.L., Peters, J.G., D., R.: Broadcasting and gossiping. In: Handbook of Graph Theory, pp. 1477\u20131494. Chapman and Hall (2013)","DOI":"10.1201\/b16132-87"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-540-73545-8_37","volume-title":"Computing and Combinatorics","author":"H Harutyunyan","year":"2007","unstructured":"Harutyunyan, H., Maraachlian, E.: Linear algorithm for broadcasting in unicyclic graphs. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 372\u2013382. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73545-8_37"},{"issue":"3","key":"20_CR18","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)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"20_CR19","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)","journal-title":"Networks"},{"key":"20_CR20","series-title":"Applied Optimization","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-1-4757-2491-2_5","volume-title":"Combinatorial Network Theory","author":"J Hromkovi\u010d","year":"1996","unstructured":"Hromkovi\u010d, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in interconnection networks (broadcasting & gossiping). In: Du, D.Z., Hsu, D.F. (eds.) Combinatorial Network Theory. Applied Optimization, vol. 1, pp. 125\u2013212. Springer, Boston (1996). https:\/\/doi.org\/10.1007\/978-1-4757-2491-2_5"},{"issue":"1\u20132","key":"20_CR21","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(94)00230-G","volume":"147","author":"K Jansen","year":"1995","unstructured":"Jansen, K., M\u00fcller, H.: The minimum broadcast time problem for several processor networks. Theoret. Comput. Sci. 147(1\u20132), 69\u201385 (1995)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"20_CR22","first-page":"211","volume":"13","author":"W Lin","year":"2009","unstructured":"Lin, W., Lam, P.C.B.: Star matching and distance two labelling. Taiwan. J. Math. 13(1), 211\u2013224 (2009)","journal-title":"Taiwan. J. Math."},{"issue":"4","key":"20_CR23","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/S0195-6698(03)00030-1","volume":"24","author":"R Merris","year":"2003","unstructured":"Merris, R.: Split graphs. Eur. J. Comb. 24(4), 413\u2013430 (2003)","journal-title":"Eur. J. Comb."},{"issue":"6","key":"20_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(93)90066-I","volume":"46","author":"M Middendorf","year":"1993","unstructured":"Middendorf, M.: Minimum broadcast time is np-complete for 3-regular planar graphs and deadline 2. Inf. Process. Lett. 46(6), 281\u2013287 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"20_CR25","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discret. Math. 156(1\u20133), 291\u2013298 (1996)","journal-title":"Discret. Math."},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in o(nm) time, or better. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2013), pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"issue":"05","key":"20_CR27","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(05), 363\u2013366 (1981)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"20_CR28","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s101070100259","volume":"91","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A.: On the history of the transportation and maximum flow problems. Math. Program. 91(3), 437\u2013445 (2002)","journal-title":"Math. Program."},{"issue":"4","key":"20_CR29","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)","journal-title":"SIAM J. Comput."},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Tamura, H., Tasaki, F., Sengoku, M., Shinoda, S.: Scheduling problems for a class of parallel distributed systems. In: IEEE International Symposium on Circuits and Systems (ISCAS 2005), pp. 176\u2013179. IEEE (2005)","DOI":"10.1109\/ISCAS.2005.1464553"},{"key":"20_CR31","unstructured":"Tyshkevich, R.I., Chernyak, A.A.: Canonical partition of a graph defined by the degrees of its vertices. Isv. Akad. Nauk BSSR Ser. Fiz.-Mat. Nauk (in Russian) 5, 14\u201326 (1979)"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends\u00ae Optim. 1(4), 241\u2013433 (2015)","DOI":"10.1561\/2400000006"},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Zhang, R.Y., Lavaei, J.: Sparse semidefinite programs with near-linear time complexity. In: 2018 IEEE Conference on Decision and Control (CDC 2018), pp. 1624\u20131631. IEEE (2018)","DOI":"10.1109\/CDC.2018.8619478"},{"key":"20_CR34","unstructured":"Zheng, Y.: Chordal sparsity in control and optimization of large-scale systems. Ph.D. thesis, University of Oxford (2019)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T03:33:28Z","timestamp":1729308808000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","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":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}