{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:20:35Z","timestamp":1759796435820,"version":"build-2065373602"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T00:00:00Z","timestamp":1755561600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T00:00:00Z","timestamp":1755561600000},"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":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00453-025-01329-5","type":"journal-article","created":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T06:34:18Z","timestamp":1755585258000},"page":"1864-1898","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Path Set Packing"],"prefix":"10.1007","volume":"87","author":[{"given":"N. R.","family":"Aravind","sequence":"first","affiliation":[]},{"given":"Roopam","family":"Saxena","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,19]]},"reference":[{"issue":"16","key":"1329_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved kernelization algorithm for r-set packing. Inf. Process. Lett. 110(16), 621\u2013624 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.04.020","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1329_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989). https:\/\/doi.org\/10.1016\/0166-218X(89)90031-0","journal-title":"Discrete Appl. Math."},{"key":"1329_CR3","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2019.10.019","volume":"278","author":"S Bessy","year":"2020","unstructured":"Bessy, S., Bougeret, M., Chaplick, S., Gon\u00e7alves, D., Paul, C.: On independent set in B1-EPG graphs. Discrete Appl. Math. 278, 62\u201372 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.10.019","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1329_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theor. Comput. Sci."},{"key":"1329_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1329_CR6","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory. In: Graduate Texts in Mathematics, 4th edn, vol. 173. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"1329_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"1329_CR8","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. In: Texts in Computer Science. Springer (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"1329_CR9","doi-asserted-by":"publisher","unstructured":"Epstein, D., Golumbic, M.C., Morgenstern, G.: Approximation algorithms for B1-EPG graphs. In: Dehne, F., Solis-Oba, R., Sack, J. (eds.) Algorithms and Data Structures\u201413th International Symposium, WADS 2013, London, ON, Canada, August 12\u201314, 2013. Proceedings. Lecture Notes in Computer Science, vol.\u00a08037, pp. 328\u2013340. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-40104-6_29","DOI":"10.1007\/978-3-642-40104-6_29"},{"issue":"1","key":"1329_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.09.065","journal-title":"Theor. Comput. Sci."},{"key":"1329_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-30140-0_29","volume-title":"Algorithms\u2014ESA 2004","author":"MR Fellows","year":"2004","unstructured":"Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. In: Albers, S., Radzik, T. (eds.) Algorithms\u2014ESA 2004, pp. 311\u2013322. Springer, Berlin (2004)"},{"key":"1329_CR12","doi-asserted-by":"publisher","unstructured":"Fox, J., Pach, J.: Computing the independence number of intersection graphs. In: Randall, D. (ed.) Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23\u201325, 2011. pp. 1161\u20131165. SIAM (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.87","DOI":"10.1137\/1.9781611973082.87"},{"issue":"4","key":"1329_CR13","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is \\$np\\$-complete. SIAM J. Appl. Math. 32 (4), 826\u2013834 (1977). https:\/\/doi.org\/10.1137\/0132071","journal-title":"SIAM J. Appl. Math."},{"key":"1329_CR14","doi-asserted-by":"publisher","unstructured":"Gima, T., Hanaka, T., Kobayashi, Y., Otachi, Y., Shirai, T., Suzuki, A., Tamura, Y., Zhou, X.: On the complexity of list h-packing for sparse graph classes. In: Uehara, R., Yamanaka, K., Yen, H. (eds.) WALCOM: Algorithms and Computation\u201418th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18\u201320, 2024, Proceedings. Lecture Notes in Computer Science, vol. 14549, pp. 421\u2013435. Springer (2024). https:\/\/doi.org\/10.1007\/978-981-97-0566-5_30","DOI":"10.1007\/978-981-97-0566-5_30"},{"issue":"2","key":"1329_CR15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0012-365X(85)90043-3","volume":"55","author":"MC Golumbic","year":"1985","unstructured":"Golumbic, M.C., Jamison, R.E.: Edge and vertex intersection of paths in a tree. Discrete Math. 55(2), 151\u2013159 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90043-3","journal-title":"Discrete Math."},{"issue":"1","key":"1329_CR16","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0095-8956(85)90088-7","volume":"38","author":"MC Golumbic","year":"1985","unstructured":"Golumbic, M.C., Jamison, R.E.: The edge intersection graphs of paths in a tree. J. Comb. Theory Ser. B 38(1), 8\u201322 (1985). https:\/\/doi.org\/10.1016\/0095-8956(85)90088-7","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"1329_CR17","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1002\/net.20305","volume":"54","author":"MC Golumbic","year":"2009","unstructured":"Golumbic, M.C., Lipshteyn, M., Stern, M.: Edge intersection graphs of single bend paths on a grid. Networks 54(3), 130\u2013138 (2009). https:\/\/doi.org\/10.1002\/net.20305","journal-title":"Networks"},{"key":"1329_CR18","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 160\u2013169. SODA \u201995, Society for Industrial and Applied Mathematics, USA (1995)"},{"key":"1329_CR19","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BFb0055051","volume-title":"Automata, Languages and Programming","author":"MM Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Independent sets with domination constraints. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) Automata, Languages and Programming. ICALP 1998. Lecture Notes in Computer Science, vol 1443, pp. 176\u2013187. Springer, Berlin"},{"key":"1329_CR20","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.dam.2013.10.035","volume":"167","author":"D Heldt","year":"2014","unstructured":"Heldt, D., Knauer, K., Ueckerdt, T.: Edge-intersection graphs of grid paths: the bend-number. Discrete Appl. Math. 167, 144\u2013162 (2014). https:\/\/doi.org\/10.1016\/j.dam.2013.10.035","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1329_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.7155\/jgaa.00413","volume":"21","author":"B Jansen","year":"2017","unstructured":"Jansen, B.M.P.: On structural parameterizations of hitting set: hitting paths in graphs using 2-sat. J. Graph Algorithms Appl. 21(2), 219\u2013243 (2017). https:\/\/doi.org\/10.7155\/jgaa.00413","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"1329_CR22","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jalgor.2003.07.001","volume":"50","author":"W Jia","year":"2004","unstructured":"Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Algorithms 50(1), 106\u2013117 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2003.07.001","journal-title":"J. Algorithms"},{"issue":"2","key":"1329_CR23","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/s00453-012-9671-1","volume":"68","author":"F Kammer","year":"2014","unstructured":"Kammer, F., Tholey, T.: Approximation algorithms for intersection graphs. Algorithmica 68(2), 312\u2013336 (2014). https:\/\/doi.org\/10.1007\/s00453-012-9671-1","journal-title":"Algorithmica"},{"issue":"1","key":"1329_CR24","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.ipl.2004.12.005","volume":"94","author":"I Koutis","year":"2005","unstructured":"Koutis, I.: A faster parameterized algorithm for set packing. Inf. Process. Lett. 94(1), 7\u20139 (2005). https:\/\/doi.org\/10.1016\/j.ipl.2004.12.005","journal-title":"Inf. Process. Lett."},{"key":"1329_CR25","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"2","key":"1329_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221\u2013232 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90051-2","journal-title":"Discrete Math."},{"issue":"4","key":"1329_CR27","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1016\/j.disopt.2008.07.002","volume":"5","author":"J Wang","year":"2008","unstructured":"Wang, J., Liu, Y.: Parameterized algorithms for weighted matching and packing problems. Discrete Optim. 5(4), 748\u2013754 (2008). https:\/\/doi.org\/10.1016\/j.disopt.2008.07.002","journal-title":"Discrete Optim."},{"key":"1329_CR28","doi-asserted-by":"publisher","unstructured":"Xu, C., Zhang, G.: The path set packing problem. In: Wang, L., Zhu, D. (eds.) Computing and Combinatorics\u201424th International Conference, COCOON 2018, Qing Dao, China, July 2\u20134, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10976, pp. 305\u2013315. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-94776-1_26","DOI":"10.1007\/978-3-319-94776-1_26"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01329-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01329-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01329-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:08:00Z","timestamp":1759738080000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01329-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,19]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1329"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01329-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,19]]},"assertion":[{"value":"12 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}