{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T14:23:53Z","timestamp":1768314233934,"version":"3.49.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031522123","type":"print"},{"value":"9783031522130","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-52213-0_16","type":"book-chapter","created":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T10:02:29Z","timestamp":1705140149000},"page":"224-238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Star Covers and\u00a0Star Partitions of\u00a0Cographs and\u00a0Butterfly-free Graphs"],"prefix":"10.1007","author":[{"given":"Joyashree","family":"Mondal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Vijayakumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,14]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2019.01.002","volume":"33","author":"G Andreatta","year":"2019","unstructured":"Andreatta, G., De Francesco, C., De Giovanni, L., Serafini, P.: Star partitions on graphs. Discrete. Optim. 33, 1\u201318 (2019)","journal-title":"Discrete. Optim."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230190206","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas, E., Yu, C.S.: On graphs with polynomially solvable maximal-weight clique problem. Networks 19, 247\u2013253 (1989)","journal-title":"Networks"},{"key":"16_CR3","unstructured":"Bang-Jensen, J., Huang, J., MacGillivray, G., Yeo, A.: Domination in convex bipartite and convex-round graphs. Technical report, University of Southern Denmark (1999)"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/jgt.22062","volume":"85","author":"R van Bevern","year":"2017","unstructured":"van Bevern, R., et al.: Partitioning perfect graphs into stars. J. Graph Theory 85, 297\u2013335 (2017)","journal-title":"J. Graph Theory"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39, 543\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BFb0028791","volume-title":"Fundamentals of Computation Theory","author":"A Brandst\u00e4dt","year":"1985","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the restriction of some NP-complete graph problems to permutation graphs. In: Budach, L. (ed.) FCT 1985. LNCS, vol. 199, pp. 53\u201362. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/BFb0028791"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","volume":"4","author":"EJ Cockayne","year":"1975","unstructured":"Cockayne, E.J., Goodman, S., Hedetniemi, S.T.: A linear algorithm for the domination number of a tree. Inform. Process. Lett. 4, 41\u201344 (1975)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"16_CR8","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0020-0190(90)90147-P","volume":"36","author":"P Damaschke","year":"1990","unstructured":"Damaschke, P., M\u00fcller, H., Kratch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36, 231\u2013236 (1990)","journal-title":"Inf. Process. Lett."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Divya, D., Vijayakumar, S.: On star partition of split graphs. In: Proceedings of the 10th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM (2024). Accepted","DOI":"10.1007\/978-3-031-52213-0_15"},{"issue":"4","key":"16_CR11","doi-asserted-by":"publisher","first-page":"1166","DOI":"10.1137\/S0097539792229507","volume":"26","author":"D Dor","year":"1997","unstructured":"Dor, D., Tarsi, M.: Graph decomposition is NP-complete: a complete proof of Holyer\u2019s conjecture. SIAM J. Comput. 26(4), 1166\u20131187 (1997)","journal-title":"SIAM J. Comput."},{"key":"16_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Undegraduate Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Undegraduate Texts in Computer Science. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"3","key":"16_CR13","first-page":"203","volume":"16","author":"O Duginov","year":"2014","unstructured":"Duginov, O.: Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs. Discrete Math. Theor. Comput. Sci. 16(3), 203\u2013214 (2014)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M Farber","year":"1985","unstructured":"Farber, M., Keil, J.M.: Domination in permutation graphs. J. Algorithms 6, 309\u2013321 (1985)","journal-title":"J. Algorithms"},{"key":"16_CR15","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0012-365X(96)00121-5","volume":"173","author":"AK Kelmans","year":"1997","unstructured":"Kelmans, A.K.: Optimal packing of stars in a graph. Discrete Math. 173, 97\u2013127 (1997)","journal-title":"Discrete Math."},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Hell, P.: On the completeness of a generalized matching problem. In: Lipton, R., Burkhard, W., Savitch, W., Friedman, E., Aho, A., (eds.) (STOC 1978) 10th ACM Symposium on Theory of Computing, pp. 240\u2013245 (1978)","DOI":"10.1145\/800133.804353"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in $$P_5$$-free graphs in polynomial time. In: Proceedings of the 25th ACM-SIAM Symposium On Discrete Algorithms, SODA, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F Maffray","year":"1996","unstructured":"Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discret. Math. 162, 313\u2013317 (1996)","journal-title":"Discret. Math."},{"key":"16_CR20","unstructured":"Mondal, J., Vijayakumar, S.: Star covers and star partitions of double-split graphs. J. Comb. Optim. Accepted"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2006.12.004","volume":"35","author":"J Monnot","year":"2007","unstructured":"Monnot, J., Toulouse, S.: The path partition problem and related problems in bipartite graphs. Oper. Res. Lett. 35, 677\u2013684 (2007)","journal-title":"Oper. Res. Lett."},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H M\u00fcller","year":"1987","unstructured":"M\u00fcller, H., Brandst\u00e4dt, A.: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoret. Comput. Sci. 53, 257\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52, 203\u2013225 (2008)","journal-title":"Algorithmica"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.dam.2021.04.015","volume":"319","author":"MA Shalu","year":"2022","unstructured":"Shalu, M.A., Vijayakumar, S., Sandhya, T.P., Mondal, J.: Star partition of graphs. Discret. Appl. Math. 319, 81\u201391 (2022)","journal-title":"Discret. Appl. Math."},{"key":"16_CR25","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"16_CR26","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, New Jersey (2000)","edition":"2"},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10, 310\u2013327 (1981)","journal-title":"SIAM J. Comput."},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-52213-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T05:22:26Z","timestamp":1768281746000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-52213-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031522123","9783031522130"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-52213-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"14 January 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bhilai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.iitbhilai.ac.in\/caldam2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}