{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T04:21:43Z","timestamp":1769228503281,"version":"3.49.0"},"reference-count":12,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"vor","delay-in-days":7,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771080"],"award-info":[{"award-number":["11771080"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2021,6,23]]},"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>Let \u210b be a family of graphs. An \u210b-packing of a graph <jats:italic>G<\/jats:italic> is a set {<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>,\u2026,<jats:italic>G<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>} of disjoint subgraphs of <jats:italic>G<\/jats:italic> such that each <jats:italic>G<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub> is isomorphic to some element of \u210b. An \u210b-packing of a graph <jats:italic>G<\/jats:italic> that covers the maximum number of vertices of <jats:italic>G<\/jats:italic> is called a maximum \u210b-packing of <jats:italic>G<\/jats:italic>. The \u210b-packing problem seeks to find a maximum \u210b-packing of a graph. Let <jats:italic>i<\/jats:italic> be a positive integer. An <jats:italic>i<\/jats:italic>-star is a complete bipartite graph <jats:italic>K<\/jats:italic><jats:sub>1,<jats:italic>i<\/jats:italic><\/jats:sub>. This paper investigates the \u210b-packing problem with H being a family of stars. For an arbitrary family \ud835\udcae of stars, we design a linear-time algorithm for the \ud835\udcae-packing problem in trees. Let <jats:italic>t<\/jats:italic> be a positive integer. An \u210b-packing is called a <jats:italic>t<\/jats:italic><jats:sup>+<\/jats:sup>-star packing if \u210b consists of <jats:italic>i<\/jats:italic>-stars with <jats:italic>i<\/jats:italic> \u2265 <jats:italic>t<\/jats:italic>. We show that the <jats:italic>t<\/jats:italic><jats:sup>+<\/jats:sup>-star packing problem for <jats:italic>t<\/jats:italic> \u2265 2 is NP-hard in bipartite graphs. As a consequence, the 2<jats:sup>+<\/jats:sup>-star packing problem is NP-hard even in bipartite graphs with maximum degree at most 4. Let <jats:italic>T<\/jats:italic> and <jats:italic>t<\/jats:italic> be two positive integers with <jats:italic>T<\/jats:italic> &gt; <jats:italic>t<\/jats:italic>. An \u210b-packing is called a <jats:italic>T<\/jats:italic>\\<jats:italic>t<\/jats:italic>-star packing if \u210b={<jats:italic>K<\/jats:italic><jats:sub>1,1<\/jats:sub>,<jats:italic>K<\/jats:italic><jats:sub>1,2<\/jats:sub>,\u2026,<jats:italic>K<\/jats:italic><jats:sub>1,<jats:italic>T<\/jats:italic><\/jats:sub>}\\{<jats:italic>K<\/jats:italic><jats:sub>1,<jats:italic>t<\/jats:italic><\/jats:sub>}. For <jats:italic>t<\/jats:italic> \u2265 2, we present a t\/t+1-approximation algorithm for the <jats:italic>T<\/jats:italic>\\<jats:italic>t<\/jats:italic>-star packing problem that runs in \ud835\udcaa(<jats:italic>mn<\/jats:italic><jats:sup>1\/2<\/jats:sup>) time, where <jats:italic>n<\/jats:italic> is the number of vertices and <jats:italic>m<\/jats:italic> the number of edges of the input graph. We also design a 1\/2-approximation algorithm for the 2<jats:sup>+<\/jats:sup>-star packing problem that runs in <jats:italic>\ud835\udcaa<\/jats:italic>(<jats:italic>m<\/jats:italic>) time, where <jats:italic>m<\/jats:italic> is the number of edges of the input graph. As a consequence, every connected graph with at least 3 vertices has a 2<jats:sup>+<\/jats:sup>-star packing that covers at least half of its vertices.<\/jats:p>","DOI":"10.1051\/ro\/2021096","type":"journal-article","created":{"date-parts":[[2021,6,24]],"date-time":"2021-06-24T19:14:22Z","timestamp":1624562062000},"page":"2129-2140","source":"Crossref","is-referenced-by-count":5,"title":["On star family packing of graphs"],"prefix":"10.1051","volume":"55","author":[{"given":"Mengya","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4112-0469","authenticated-orcid":false,"given":"Wensong","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"key":"R1","unstructured":"Anstee R., Personal Communication to Pavol Hell (1996)."},{"key":"R2","unstructured":"Bahenko M. and Gusakov A., New exact and approximation algorithms for the star packing problem in undirected graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. March 10\u201312, 2011, Dortmund, Germany (2011) 519\u2013530."},{"key":"R3","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/j.jctb.2007.09.004","volume":"98","author":"Brewster","year":"2008","journal-title":"J. Combin. Theory, Ser. B"},{"key":"R4","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"Chleb\u00edk","year":"2006","journal-title":"Theoret. Comput. Sci."},{"key":"R5","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)."},{"key":"R6","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1002\/jgt.20161","volume":"52","author":"Hartvigsen","year":"2006","journal-title":"J. Graph Theory"},{"key":"R7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0012-365X(84)90150-X","volume":"49","author":"Hell","year":"1984","journal-title":"Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1137\/0607024","volume":"7","author":"Hell","year":"1986","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"R9","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0401046","volume":"1","author":"Hell","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0012-365X(96)00121-5","volume":"173","author":"Kelmans","year":"1997","journal-title":"Discrete Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1006\/jctb.1993.1058","volume":"59","author":"Loebl","year":"1993","journal-title":"J. Combin. Theory Ser. B"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Ning Q., On the star packing problem. In: Vol. 576 of Proc. 1st China-USA International Graph Theory Conference (1989) 411\u2013416.","DOI":"10.1111\/j.1749-6632.1989.tb16425.x"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021096\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T08:22:11Z","timestamp":1625732531000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":12,"journal-issue":{"issue":"4"},"alternative-id":["ro210124"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2021096","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}