{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:10:51Z","timestamp":1771614651126,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T00:00:00Z","timestamp":1665446400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T00:00:00Z","timestamp":1665446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["304006"],"award-info":[{"award-number":["304006"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s11590-022-01939-w","type":"journal-article","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T04:02:55Z","timestamp":1665460975000},"page":"1435-1454","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A fast approximation algorithm for the maximum 2-packing set problem on planar graphs"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9326-7713","authenticated-orcid":false,"given":"Joel Antonio","family":"Trejo-S\u00e1nchez","sequence":"first","affiliation":[]},{"given":"Francisco A.","family":"Madera-Ram\u00edrez","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 Alberto","family":"Fern\u00e1ndez-Zepeda","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 Luis","family":"L\u00f3pez-Mart\u00ednez","sequence":"additional","affiliation":[]},{"given":"Alejandro","family":"Flores-Lamas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"issue":"3","key":"1939_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24(3), 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"1939_CR2","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.tcs.2007.09.013","volume":"389","author":"VE Alekseev","year":"2007","unstructured":"Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: Np-hard graph problems and boundary classes of graphs. Theoret. Comput. Sci. 389(1\u20132), 219\u2013236 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1939_CR3","first-page":"623","volume":"20","author":"R Anand","year":"2017","unstructured":"Anand, R., Aggarwal, D., Kumar, V.: A comparative analysis of optimization solvers. J. Stat. Manag. Syst. 20(4), 623\u2013635 (2017)","journal-title":"J. Stat. Manag. Syst."},{"issue":"1","key":"1939_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM (JACM) 41(1), 153\u2013180 (1994)","journal-title":"J. ACM (JACM)"},{"key":"1939_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N.: Approximating independent sets in sparse graphs. In: proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, pp. 1\u20138. SIAM (2014)","DOI":"10.1137\/1.9781611973730.1"},{"key":"1939_CR6","unstructured":"Chandler\u00a0Sr, J.D.: Neighborhood-restricted achromatic colorings of graphs (2016)"},{"issue":"1\u20133","key":"1939_CR7","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne, E.J., Dreyer, P.A., Jr., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discret. Math. 278(1\u20133), 11\u201322 (2004)","journal-title":"Discret. Math."},{"key":"1939_CR8","doi-asserted-by":"crossref","unstructured":"Ding, Y., Wang, J.Z., Srimani, P.K.: Self-stabilizing algorithm for maximal 2-packing with safe convergence in an arbitrary graph. In: 2014 IEEE international parallel & distributed processing symposium workshops, pp. 747\u2013754. IEEE (2014)","DOI":"10.1109\/IPDPSW.2014.86"},{"issue":"2","key":"1939_CR9","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2004","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219\u2013225 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"1939_CR10","doi-asserted-by":"crossref","unstructured":"Feitelson, D.G.: Packing schemes for gang scheduling. In: workshop on job scheduling strategies for parallel processing, pp. 89\u2013110. Springer (1996)","DOI":"10.1007\/BFb0022289"},{"key":"1939_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2017.11.030","volume":"725","author":"A Flores-Lamas","year":"2018","unstructured":"Flores-Lamas, A., Fern\u00e1ndez-Zepeda, J.A., Trejo-S\u00e1nchez, J.A.: Algorithm to find a maximum 2-packing set in a cactus. Theoret. Comput. Sci. 725, 31\u201351 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"1939_CR12","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.jpdc.2020.03.016","volume":"142","author":"A Flores-Lamas","year":"2020","unstructured":"Flores-Lamas, A., Fern\u00e1ndez-Zepeda, J.A., Trejo-S\u00e1nchez, J.A.: A distributed algorithm for a maximal 2-packing set in Halin graphs. J. Parallel Distribut. Comput. 142, 62\u201376 (2020)","journal-title":"J. Parallel Distribut. Comput."},{"key":"1939_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer-Verlag, Berlin, Heidelberg (2010)","edition":"1"},{"issue":"2","key":"1939_CR14","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput. 36(2), 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"1939_CR15","first-page":"1","volume":"11","author":"M Gairing","year":"2004","unstructured":"Gairing, M., Geist, R.M., Hedetniemi, S.T., Kristiansen, P.: A self-stabilizing algorithm for maximal 2-packing. Nordic J. Comput. 11, 1\u201311 (2004)","journal-title":"Nordic J. Comput."},{"issue":"03n04","key":"1939_CR16","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1142\/S0129626404001970","volume":"14","author":"M Gairing","year":"2004","unstructured":"Gairing, M., Goddard, W., Hedetniemi, S.T., Kristiansen, P., McRae, A.A.: Distance-two information in self-stabilizing algorithms. Parallel Process. Lett. 14(03n04), 387\u2013398 (2004)","journal-title":"Parallel Process. Lett."},{"key":"1939_CR17","unstructured":"Garey, M., Johnson, D.: Computers and intractability - a guide to np-completeness.(1979). Google Scholar pp. 155\u2013158"},{"issue":"1\u20132","key":"1939_CR18","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.tcs.2008.02.009","volume":"399","author":"W Goddard","year":"2008","unstructured":"Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Trevisan, V.: Distance-k knowledge in self-stabilizing algorithms. Theoret. Comput. Sci. 399(1\u20132), 118\u2013127 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1939_CR19","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1080\/0952813X.2013.782347","volume":"25","author":"A Gogna","year":"2013","unstructured":"Gogna, A., Tayal, A.: Metaheuristics: review and application. J. Experiment. & Theor. Artif. Intell. 25(4), 503\u2013526 (2013)","journal-title":"J. Experiment. & Theor. Artif. Intell."},{"issue":"9","key":"1939_CR20","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.3390\/electronics9091541","volume":"9","author":"M Gonz\u00e1lez","year":"2020","unstructured":"Gonz\u00e1lez, M., L\u00f3pez-Esp\u00edn, J.J., Aparicio, J.: A parallel algorithm for matheuristics: a comparison of optimization solvers. Electronics 9(9), 1541 (2020)","journal-title":"Electronics"},{"key":"1939_CR21","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual (2021). http:\/\/www.gurobi.com"},{"issue":"12","key":"1939_CR22","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"WK Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497\u20131514 (1980)","journal-title":"Proc. IEEE"},{"issue":"1\u20133","key":"1939_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0166-218X(99)00124-9","volume":"99","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u0131l, J., Telle, J.A.: Independent sets with domination constraints. Discret. Appl. Math. 99(1\u20133), 39\u201354 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1939_CR24","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1939_CR25","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM (JACM) 21(4), 549\u2013568 (1974)","journal-title":"J. ACM (JACM)"},{"key":"1939_CR26","unstructured":"IBM: Cplex (1999). https:\/\/www.ibm.com\/mx-es\/analytics\/cplex-optimizer"},{"issue":"4","key":"1939_CR27","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10732-017-9337-x","volume":"23","author":"S Lamm","year":"2017","unstructured":"Lamm, S., Sanders, P., Schulz, C., Strash, D., Werneck, R.F.: Finding near-optimal independent sets at scale. J. Heuristics 23(4), 207\u2013229 (2017)","journal-title":"J. Heuristics"},{"key":"1939_CR28","unstructured":"Lozin, V., Milani\u010d, M.: Maximum independent sets in graphs of low degree. In: proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, pp. 874\u2013880. (2007)"},{"key":"1939_CR29","doi-asserted-by":"crossref","unstructured":"Manne, F., Mjelde, M.: A memory efficient self-stabilizing algorithm for maximal $$k$$-packing. In: symposium on self-stabilizing systems, pp. 428\u2013439. Springer (2006)","DOI":"10.1007\/978-3-540-49823-0_30"},{"key":"1939_CR30","unstructured":"Mjelde, M.: $$k$$-packing and $$k$$-domination on tree graphs. Master\u2019s thesis, The University of Bergen (2004)"},{"key":"1939_CR31","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications 31 (2002)"},{"issue":"13","key":"1939_CR32","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.ipl.2012.03.018","volume":"112","author":"Z Shi","year":"2012","unstructured":"Shi, Z.: A self-stabilizing algorithm to maximal 2-packing with improved complexity. Inf. Process. Lett. 112(13), 525\u2013531 (2012)","journal-title":"Inf. Process. Lett."},{"key":"1939_CR33","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1007\/978-1-4419-1153-7_1167","volume":"62","author":"K S\u00f6rensen","year":"2013","unstructured":"S\u00f6rensen, K., Glover, F.: Metaheuristics. Encyclopedia of operations research and management science 62, 960\u2013970 (2013)","journal-title":"Encyclopedia of operations research and management science"},{"issue":"1","key":"1939_CR34","first-page":"173","volume":"30","author":"JA Trejo-S\u00e1nchez","year":"2020","unstructured":"Trejo-S\u00e1nchez, J.A., Fajardo-Delgado, D., Gutierrez-Garcia, J.O.: A genetic algorithm for the maximum 2-packing set problem. Int. J. Appl. Math. Comput. Sci. 30(1), 173\u2013184 (2020)","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"1939_CR35","doi-asserted-by":"crossref","unstructured":"Trejo-S\u00e1nchez, J.A., Fern\u00e1ndez-Zepeda, J.A.: A self-stabilizing algorithm for the maximal 2-packing in a cactus graph. In: 2012 IEEE 26th international parallel and distributed processing symposium workshops & PhD Forum, pp. 863\u2013871. IEEE (2012)","DOI":"10.1109\/IPDPSW.2012.106"},{"issue":"3","key":"1939_CR36","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.jpdc.2013.12.002","volume":"74","author":"JA Trejo-S\u00e1nchez","year":"2014","unstructured":"Trejo-S\u00e1nchez, J.A., Fern\u00e1ndez-Zepeda, J.A.: Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs. J. Parallel Distribut Comput. 74(3), 2193\u20132202 (2014)","journal-title":"J. Parallel Distribut Comput."},{"issue":"08","key":"1939_CR37","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1142\/S012905411750037X","volume":"28","author":"JA Trejo-S\u00e1nchez","year":"2017","unstructured":"Trejo-S\u00e1nchez, J.A., Fern\u00e1ndez-Zepeda, J.A., Ram\u00edrez-Pacheco, J.C.: A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler. Int. J. Found. Comput. Sci. 28(08), 1021\u20131045 (2017)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"1939_CR38","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1016\/j.jpdc.2011.12.008","volume":"72","author":"V Turau","year":"2012","unstructured":"Turau, V.: Efficient transformation of distance-2 self-stabilizing algorithms. J. Parallel Distribut. Comput. 72(4), 603\u2013612 (2012)","journal-title":"J. Parallel Distribut. Comput."},{"key":"1939_CR39","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer Science & Business Media, Springer-Verlag GmbH, Heidelberg, Zweigniederlassung der Springer-Verlag GmbH, Berlin, Tiergartenstrasse 17, D-69121 Heidelberg (2013)"},{"key":"1939_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, USA (2011)"},{"key":"1939_CR41","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Exact algorithms for np-hard problems: A survey. In: Combinatorial optimization\u2013eureka, you shrink!, pp. 185\u2013207. Springer, Springer-Verlag GmbH, Heidelberg, Zweigniederlassung der Springer-Verlag GmbH, Berlin, Tiergartenstrasse 17, D-69121 Heidelberg (2003)","DOI":"10.1007\/3-540-36478-1_17"},{"issue":"1","key":"1939_CR42","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s11590-015-0876-5","volume":"10","author":"B Yelbay","year":"2016","unstructured":"Yelbay, B., Birbil, \u015e\u0130, B\u00fclb\u00fcl, K., Jamil, H.: Approximating the minimum hub cover problem on planar graphs. Optimization Lett. 10(1), 33\u201345 (2016)","journal-title":"Optimization Lett."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01939-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01939-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01939-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T15:15:50Z","timestamp":1685114150000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01939-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,11]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1939"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01939-w","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,11]]},"assertion":[{"value":"18 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}