{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T11:00:45Z","timestamp":1782644445160,"version":"3.54.5"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T00:00:00Z","timestamp":1539129600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["307026\/2013-2"],"award-info":[{"award-number":["307026\/2013-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007351","name":"Secretaria de Ciencia y Tecnica, Universidad de Buenos Aires","doi-asserted-by":"publisher","award":["UBACyT Grant 20020120100058"],"award-info":[{"award-number":["UBACyT Grant 20020120100058"]}],"id":[{"id":"10.13039\/501100007351","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003074","name":"Agencia Nacional de Promoci\u00f3n Cient\u00edfica y Tecnol\u00f3gica","doi-asserted-by":"publisher","award":["PICT ANPCyT 2010-1970"],"award-info":[{"award-number":["PICT ANPCyT 2010-1970"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003074","name":"Agencia Nacional de Promoci\u00f3n Cient\u00edfica y Tecnol\u00f3gica","doi-asserted-by":"publisher","award":["PICT ANPCyT 2013-2205"],"award-info":[{"award-number":["PICT ANPCyT 2013-2205"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s11590-018-1335-x","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T07:54:44Z","timestamp":1539158084000},"page":"369-394","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Modelling and solving the perfect edge domination problem"],"prefix":"10.1007","volume":"14","author":[{"given":"Vinicius L.","family":"do Forte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Min Chih","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abilio","family":"Lucena","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3897-3356","authenticated-orcid":false,"given":"Nelson","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Veronica A.","family":"Moyano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,10,10]]},"reference":[{"key":"1335_CR1","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.dam.2016.01.012","volume":"234","author":"E Andrade","year":"2018","unstructured":"Andrade, E., Cardoso, D.M., Medina, L., Rojo, O.: On the dominating induced matching problem: spectral results and sharp bounds. Discrete Appl. Math. 234, 22\u201331 (2018). (Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1335_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"N Biggs","year":"1973","unstructured":"Biggs, N.: Perfect codes in graphs. J. Comb. Theory Ser. B 15(3), 289\u2013296 (1973)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"1335_CR3","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1002\/net.21516","volume":"62","author":"M Bodur","year":"2013","unstructured":"Bodur, M., Ekim, T., Taskin, Z.C.: Decomposition algorithms for solving the minimum weight maximal matching problem. Networks 62(4), 273\u2013287 (2013)","journal-title":"Networks"},{"key":"1335_CR4","unstructured":"Bornd\u00f6rfer, R.: Aspects of set packing, partitioning, and covering. Ph.D. thesis (1998)"},{"key":"1335_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: Proceedings of the 9th Latin American conference on Theoretical Informatics, LATIN\u201910, pp. 650\u2013661. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-12200-2_56"},{"key":"1335_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: Algorithms and Computation\u201423rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19\u201321 Dec 2012. Proceedings, pp. 267\u2013277 (2012)","DOI":"10.1007\/978-3-642-35261-4_30"},{"key":"1335_CR7","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings for \n$$P_7$$\n\n\n\n\nP\n7\n\n\n\n\n-free graphs in linear Time. CoRR (2011). \narXiv:1106.2772"},{"issue":"4","key":"1335_CR8","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s00453-016-0150-y","volume":"77","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Finding dominating induced matchings in p\n$${}_{\\text{8 }}$$\n\n\n\n\n\n\n8\n\n\n\n\n\n\n-free graphs in polynomial time. Algorithmica 77(4), 1283\u20131302 (2017)","journal-title":"Algorithmica"},{"issue":"15","key":"1335_CR9","doi-asserted-by":"publisher","first-page":"3060","DOI":"10.1016\/j.dam.2008.01.021","volume":"156","author":"DM Cardoso","year":"2008","unstructured":"Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Appl. Math. 156(15), 3060\u20133065 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"1335_CR10","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/j.dam.2010.03.011","volume":"159","author":"DM Cardoso","year":"2011","unstructured":"Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159(7), 521\u2013531 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1335_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.7151\/dmgt.1006","volume":"15","author":"GJ Chang","year":"1995","unstructured":"Chang, G.J., Hwang, S.: The edge domination problem. Discuss. Math. Graph Theory 15(1), 51\u201357 (1995)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1335_CR12","doi-asserted-by":"crossref","unstructured":"Demange, M., Ekim, T.: Minimum maximal matching is np-hard in regular bipartite graphs. In: Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi\u2019an, China, 25\u201329 April 2008. Proceedings, pp. 364\u2013374 (2008)","DOI":"10.1007\/978-3-540-79228-4_32"},{"issue":"5","key":"1335_CR13","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"DL Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48(5), 221\u2013228 (1993)","journal-title":"Inf. Process. Lett."},{"key":"1335_CR14","unstructured":"Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de\u00a0Werra, D.: Dominating induced matchings in graphs containing no long claw. CoRR (2015). \narXiv:1505.02558"},{"issue":"3","key":"1335_CR15","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"DJ Horton","year":"1993","unstructured":"Horton, D.J., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6(3), 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"1335_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/0095-8956(91)90057-Q","volume":"53","author":"JD Horton","year":"1991","unstructured":"Horton, J.D., Bower, I.Z.: Symmetric y-graphs and h-graphs. J. Comb. Theory Ser. B 53, 114\u2013129 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1335_CR17","unstructured":"IBM. IBM ILOG CPLEX Optimization Studio V12.6.0 documentation (2017)"},{"key":"1335_CR18","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.endm.2009.02.018","volume":"32","author":"N Korpelainen","year":"2009","unstructured":"Korpelainen, N.: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. Electron. Notes Discrete Math. 32, 133\u2013140 (2009)","journal-title":"Electron. Notes Discrete Math."},{"issue":"1\u20132","key":"1335_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s10479-017-2664-3","volume":"264","author":"MC Lin","year":"2018","unstructured":"Lin, M.C., Lozin, V., Moyano, V.A., Szwarcfiter, J.L.: Perfect edge domination: hard and solvable cases. Ann. Oper. Res. 264(1\u20132), 287\u2013305 (2018)","journal-title":"Ann. Oper. Res."},{"issue":"10","key":"1335_CR20","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.ipl.2014.04.012","volume":"114","author":"MC Lin","year":"2014","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Fast algorithms for some dominating induced matching problems. Inf. Process. Lett. 114(10), 524\u2013528 (2014)","journal-title":"Inf. Process. Lett."},{"key":"1335_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.endm.2015.07.051","volume":"50","author":"MC Lin","year":"2015","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Efficient and perfect domination on circular-arc graphs. Electron. Notes Discrete Math. 50, 307\u2013312 (2015)","journal-title":"Electron. Notes Discrete Math."},{"issue":"3","key":"1335_CR22","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1007\/s00453-015-0095-6","volume":"77","author":"MC Lin","year":"2017","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Exact algorithms for minimum weighted dominating induced matching. Algorithmica 77(3), 642\u2013660 (2017)","journal-title":"Algorithmica"},{"key":"1335_CR23","volume-title":"Introduction to Combinatorial Mathematics","author":"CL Liu","year":"1968","unstructured":"Liu, C.L.: Introduction to Combinatorial Mathematics. McGraw-Hill, New York (1968)"},{"key":"1335_CR24","doi-asserted-by":"crossref","unstructured":"Livingston, M., Stout, Q.F.: Distributing resources in hypercube computers. In: Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, Vol. 1, C3P, pp. 222\u2013231. ACM, New York (1988)","DOI":"10.1145\/62297.62324"},{"issue":"3","key":"1335_CR25","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(01)00198-6","volume":"119","author":"CL Lu","year":"2002","unstructured":"Lu, C.L., Ko, M., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119(3), 227\u2013250 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"1335_CR26","first-page":"203","volume":"87","author":"CL Lu","year":"1998","unstructured":"Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87(1\u20133), 203\u2013211 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1335_CR27","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/0377-2217(88)90258-5","volume":"33","author":"MB Richey","year":"1988","unstructured":"Richey, M.B., Parker, R.G.: Minimum-maximal matching in series\u2013parallel graphs. Eur. J. Oper. Res. 33(1), 98\u2013105 (1988)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1335_CR28","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","volume":"56","author":"A Srinivasan","year":"1995","unstructured":"Srinivasan, A., Madhukar, K., Nagavamsi, P., Rangan, C.P., Chang, M.-S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inf. Process. Lett. 56(3), 165\u2013171 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"1335_CR29","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s11590-011-0351-x","volume":"6","author":"ZC Taskin","year":"2012","unstructured":"Taskin, Z.C., Ekim, T.: Integer programming formulations for the minimum weighted maximal matching problem. Optim. Lett. 6(6), 1161\u20131171 (2012)","journal-title":"Optim. Lett."},{"issue":"1\u20133","key":"1335_CR30","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0012-365X(92)90300-5","volume":"109","author":"PM Weichsel","year":"1992","unstructured":"Weichsel, P.M.: Distance regular subgraphs of a cube. Discrete Math. 109(1\u20133), 297\u2013306 (1992)","journal-title":"Discrete Math."},{"issue":"5","key":"1335_CR31","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1002\/jgt.3190180506","volume":"18","author":"PM Weichsel","year":"1994","unstructured":"Weichsel, P.M.: Dominating sets in n-cubes. J. Graph Theory 18(5), 479\u2013488 (1994)","journal-title":"J. Graph Theory"},{"key":"1335_CR32","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.dam.2015.04.012","volume":"190\u2013191","author":"M Xiao","year":"2015","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for dominating induced matching based on graph partition. Discrete Appl. Math. 190\u2013191, 147\u2013162 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1335_CR33","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"1335_CR34","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"C-C Yen","year":"1996","unstructured":"Yen, C.-C., Lee, R.C.T.: The weighted perfect domination problem and its variants. Discrete Appl. Math. 66(2), 147\u2013160 (1996)","journal-title":"Discrete Appl. Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-018-1335-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-018-1335-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-018-1335-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T21:04:22Z","timestamp":1581627862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-018-1335-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,10]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["1335"],"URL":"https:\/\/doi.org\/10.1007\/s11590-018-1335-x","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,10]]},"assertion":[{"value":"19 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}