{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:18:49Z","timestamp":1742930329270,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":31,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819628445"},{"type":"electronic","value":"9789819628452"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-2845-2_15","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:59:47Z","timestamp":1740067187000},"page":"229-243","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for\u00a0Non-sequential Star Packing Problems"],"prefix":"10.1007","author":[{"given":"Mengyuan","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"An","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingyang","family":"Gong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"15_CR1","unstructured":"Bahenko, M., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: Proceedings of STACS 2011, pp. 519\u2013530 (2011)"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0196-6774(90)90001-U","volume":"11","author":"F Berman","year":"1990","unstructured":"Berman, F., Johnson, D., Leighton, T., Shor, P.W., Snyder, L.: Generalized planar matching. J. Algorithms 11, 153\u2013184 (1990)","journal-title":"J. Algorithms"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0020-0190(02)00274-0","volume":"84","author":"A Caprara","year":"2002","unstructured":"Caprara, A., Rizzi, R.: Packing triangles in bounded degree graphs. Inf. Process. Lett. 84, 175\u2013180 (2002)","journal-title":"Inf. Process. Lett."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s10878-021-00793-3","volume":"43","author":"Y Chen","year":"2022","unstructured":"Chen, Y., et al.: Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph. J. Comb. Optim. 43, 571\u2013588 (2022)","journal-title":"J. Comb. Optim."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Grandoni, F., Mastrolilli, M.: How to sell hyperedges: the hypermatching assignment problem. In: Proceedings of SODA 2013, pp. 342\u2013351 (2013)","DOI":"10.1137\/1.9781611973105.25"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Eto, H., Ito, T., Liu, Z., Miyano, E.: Approximation algorithm for the distance-$$3$$ independent set problem on cubic graphs. In: Proceedings of WALCOM 2017, pp. 228\u2013240 (2017)","DOI":"10.1007\/978-3-319-53925-6_18"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., Yu, H.: Approximating the $$k$$-set packing problem by local improvements. In: Proceedings of ISCO 2014, pp. 408\u2013420 (2014)","DOI":"10.1007\/978-3-319-14115-2_35"},{"key":"15_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco (1979)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10107-004-0505-z","volume":"100","author":"AV Goldberg","year":"2004","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100, 537\u2013568 (2004)","journal-title":"Math. Program."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Gong, M., Chen, Z.-Z., Lin, G., Wang, L.: An approximation algorithm for covering vertices by $$4^+$$-paths. In: Proceedings of COCOA 2023. LNCS, vol. 14461, pp. 459\u2013470 (2023)","DOI":"10.1007\/978-3-031-49611-0_33"},{"key":"15_CR11","unstructured":"Gong, M., Fan, J., Lin, G., Miyano, E.: Approximation algorithms for covering vertices by long paths. In: Proceedings of MFCS 2022, pp. 53:1\u201353:14 (2022)"},{"key":"15_CR12","unstructured":"Helfgott, H.A., Bajpai, J., Dona, D.: Graph isomorphisms in quasi-polynomial time (2017). https:\/\/arXiv.org\/abs\/1710.04574"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0012-365X(84)90150-X","volume":"49","author":"P Hell","year":"1984","unstructured":"Hell, P., Kirkpatrick, D.G.: Packing by cliques and by finite families of graphs. Discret. Math. 49, 45\u201359 (1984)","journal-title":"Discret. Math."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/0607024","volume":"45","author":"P Hell","year":"1986","unstructured":"Hell, P., Kirkpatrick, D.G.: Packing by complete bipartite graphs. SIAM J. Algebraic Discret. Methods 45, 199\u2013209 (1986)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1137\/0401046","volume":"1","author":"P Hell","year":"1988","unstructured":"Hell, P., Kirkpatrick, D.G., Kratochv\u00edl, J., K\u0159\u00ed\u017e, I.: On restricted two-factors. SIAM J. Discret. Math. 1, 472\u2013484 (1988)","journal-title":"SIAM J. Discret. Math."},{"key":"15_CR16","unstructured":"Hu, M., Zhang, A., Chen, Y., Gong, M., Lin, G.: Approximation algorithms for non-sequential star packing problems (2024). https:\/\/arxiv.org\/abs\/2411.11136"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhang, A., Gao, M., Sun, J., Chen, Y.: Approximation algorithms for the $$k^+$$-star packing problem. Oper. Res. Lett. (2024). Revision requested","DOI":"10.1016\/j.orl.2025.107249"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37, 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1002\/jgt.10136","volume":"45","author":"A Kelmans","year":"2004","unstructured":"Kelmans, A., Mubayi, D.: How many disjoint $$2$$-edge paths must a cubic graph have? J. Graph Theory 45, 57\u201379 (2004)","journal-title":"J. Graph Theory"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12, 601\u2013609 (1983)","journal-title":"SIAM J. Comput."},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"3348","DOI":"10.1007\/s00453-023-01106-2","volume":"85","author":"K Kobayashi","year":"2023","unstructured":"Kobayashi, K., et al.: Path cover problems with length cost. Algorithmica 85, 3348\u20133375 (2023)","journal-title":"Algorithmica"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"2129","DOI":"10.1051\/ro\/2021096","volume":"55","author":"M Li","year":"2021","unstructured":"Li, M., Lin, W.: On star family packing of graphs. RAIRO-Oper. Res. 55, 2129\u20132140 (2021)","journal-title":"RAIRO-Oper. Res."},{"key":"15_CR23","doi-asserted-by":"publisher","first-page":"3993","DOI":"10.1007\/s11277-017-4711-4","volume":"97","author":"C Lin","year":"2017","unstructured":"Lin, C., Cui, L., Coit, D.W., Lv, M.: Performance analysis for a wireless sensor network of star topology with random nodes deployment. Wireless Pers. Commun. 97, 3993\u20134013 (2017)","journal-title":"Wireless Pers. Commun."},{"key":"15_CR24","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1006\/jctb.1993.1058","volume":"59","author":"M Loebl","year":"1993","unstructured":"Loebl, M., Poljak, S.: Efficient subgraph packing. J. Combin. Theory Ser. B 59, 106\u2013121 (1993)","journal-title":"J. Combin. Theory Ser. B"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1016\/j.disc.2007.07.100","volume":"308","author":"G Manic","year":"2008","unstructured":"Manic, G., Wakabayashi, Y.: Packing triangles in low degree graphs and indifference graphs. Discret. Math. 308, 1455\u20131471 (2008)","journal-title":"Discret. Math."},{"key":"15_CR26","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":"15_CR27","doi-asserted-by":"publisher","unstructured":"Neuwohner, M.: The limits of local search for weighted $$k$$-set packing. Math. Program. (2023). https:\/\/doi.org\/10.1007\/s10107-023-02026-3","DOI":"10.1007\/s10107-023-02026-3"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Thiery, T., Ward, J.: An improved approximation for maximum weighted $$k$$-set packing (2023). https:\/\/arXiv.org\/abs\/2301.07537","DOI":"10.1137\/1.9781611977554.ch42"},{"key":"15_CR29","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/s10878-021-00708-2","volume":"41","author":"W Xi","year":"2021","unstructured":"Xi, W., Lin, W.: On maximum P3-packing in claw-free subcubic graphs. J. Comb. Optim. 41, 694\u2013709 (2021)","journal-title":"J. Comb. Optim."},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Xi, W., Lin, W.: The maximum $$3$$-star packing problem in claw-free cubic graphs. J. Combin. Optim. 47, Article 73 (2024)","DOI":"10.1007\/s10878-024-01115-z"},{"key":"15_CR31","first-page":"128287","volume":"460","author":"W Xi","year":"2024","unstructured":"Xi, W., Lin, W., Lin, Y.: Packing $$2$$- and $$3$$-stars into cubic graphs. Appl. Math. Comput. 460, 128287 (2024)","journal-title":"Appl. Math. Comput."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-2845-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:09Z","timestamp":1740067209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-2845-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819628445","9789819628452"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-2845-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"21 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/walcom2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}