Modelling and solving the perfect edge domination problem
A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exac...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Springer Verlag
2018
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 09125caa a22009497a 4500 | ||
|---|---|---|---|
| 001 | PAPER-25280 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205718.0 | ||
| 008 | 190410s2018 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85055332381 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a do Forte, V.L. | |
| 245 | 1 | 0 | |a Modelling and solving the perfect edge domination problem |
| 260 | |b Springer Verlag |c 2018 | ||
| 270 | 1 | 0 | |m Maculan, N.; Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de JaneiroBrazil; email: maculan@cos.ufrj.br |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Andrade, E., Cardoso, D.M., Medina, L., Rojo, O., On the dominating induced matching problem: spectral results and sharp bounds (2018) Discrete Appl. Math., 234, pp. 22-31. , (Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014 | ||
| 504 | |a Biggs, N., Perfect codes in graphs (1973) J. Comb. Theory Ser. B, 15 (3), pp. 289-296 | ||
| 504 | |a Bodur, M., Ekim, T., Taskin, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem (2013) Networks, 62 (4), pp. 273-287 | ||
| 504 | |a Borndörfer, R., (1998) Aspects of Set Packing, Partitioning, and Covering, , Ph.D. thesis | ||
| 504 | |a Brandstädt, A., Hundt, C., Nevries, R., Efficient Edge Domination on Hole-Free Graphs in Polynomial Time (2010) LATIN 2010: Theoretical Informatics, pp. 650-661. , Springer Berlin Heidelberg, Berlin, Heidelberg | ||
| 504 | |a Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) Algorithms and Computation—23rd International Symposium, ISAAC 2012, pp. 267-277. , Taipei, Taiwan, 19–21 Dec 2012. Proceedings | ||
| 504 | |a Brandstädt, A., Mosca, R., (2011) Dominating Induced Matchings for P 7 -Free Graphs in Linear Time, , CoRR | ||
| 504 | |a Brandstädt, A., Mosca, R., Finding dominating induced matchings in p 8 -free graphs in polynomial time (2017) Algorithmica, 77 (4), pp. 1283-1302 | ||
| 504 | |a Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C., Efficient edge domination in regular graphs (2008) Discrete Appl. Math., 156 (15), pp. 3060-3065 | ||
| 504 | |a Cardoso, D.M., Korpelainen, N., Lozin, V.V., On the complexity of the dominating induced matching problem in hereditary classes of graphs (2011) Discrete Appl. Math., 159 (7), pp. 521-531 | ||
| 504 | |a Chang, G.J., Hwang, S., The edge domination problem (1995) Discuss. Math. Graph Theory, 15 (1), pp. 51-57 | ||
| 504 | |a Demange, M., Ekim, T., Minimum maximal matching is np-hard in regular bipartite graphs (2008) Theory and Applications of Models of Computation, 5Th International Conference, TAMC 2008, Xi’an, China, 25–29 April 2008. Proceedings, pp. 364-374 | ||
| 504 | |a Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D., Efficient edge domination problems in graphs (1993) Inf. Process. Lett., 48 (5), pp. 221-228 | ||
| 504 | |a Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D., (2015) Dominating Induced Matchings in Graphs Containing No Long Claw, , CoRR | ||
| 504 | |a Horton, D.J., Kilakos, K., Minimum edge dominating sets (1993) SIAM J. Discrete Math., 6 (3), pp. 375-387 | ||
| 504 | |a Horton, J.D., Bower, I.Z., Symmetric y-graphs and h-graphs (1991) J. Comb. Theory Ser. B, 53, pp. 114-129 | ||
| 504 | |a (2017), IBM. IBM ILOG CPLEX Optimization Studio V12.6.0 documentation; Korpelainen, N., A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs (2009) Electron. Notes Discrete Math., 32, pp. 133-140 | ||
| 504 | |a Lin, M.C., Lozin, V., Moyano, V.A., Szwarcfiter, J.L., Perfect edge domination: hard and solvable cases (2018) Ann. Oper. Res., 264 (1-2), pp. 287-305 | ||
| 504 | |a Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Fast algorithms for some dominating induced matching problems (2014) Inf. Process. Lett., 114 (10), pp. 524-528 | ||
| 504 | |a Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Efficient and perfect domination on circular-arc graphs (2015) Electron. Notes Discrete Math., 50, pp. 307-312 | ||
| 504 | |a Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Exact algorithms for minimum weighted dominating induced matching (2017) Algorithmica, 77 (3), pp. 642-660 | ||
| 504 | |a Liu, C.L., (1968) Introduction to Combinatorial Mathematics, , McGraw-Hill, New York | ||
| 504 | |a Livingston, M., Stout, Q.F., Distributing resources in hypercube computers (1988) Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, 1, pp. 222-231. , C3P, ACM, New York | ||
| 504 | |a Lu, C.L., Ko, M., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Appl. Math., 119 (3), pp. 227-250 | ||
| 504 | |a Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs (1998) Discrete Appl. Math., 87 (1-3), pp. 203-211 | ||
| 504 | |a Richey, M.B., Parker, R.G., Minimum-maximal matching in series–parallel graphs (1988) Eur. J. Oper. Res., 33 (1), pp. 98-105 | ||
| 504 | |a Srinivasan, A., Madhukar, K., Nagavamsi, P., Rangan, C.P., Chang, M.-S., Edge domination on bipartite permutation graphs and cotriangulated graphs (1995) Inf. Process. Lett., 56 (3), pp. 165-171 | ||
| 504 | |a Taskin, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem (2012) Optim. Lett., 6 (6), pp. 1161-1171 | ||
| 504 | |a Weichsel, P.M., Distance regular subgraphs of a cube (1992) Discrete Math., 109 (1-3), pp. 297-306 | ||
| 504 | |a Weichsel, P.M., Dominating sets in n-cubes (1994) J. Graph Theory, 18 (5), pp. 479-488 | ||
| 504 | |a Xiao, M., Nagamochi, H., Exact algorithms for dominating induced matching based on graph partition (2015) Discrete Appl. Math., 190-191, pp. 147-162 | ||
| 504 | |a Yannakakis, M., Gavril, F., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372 | ||
| 504 | |a Yen, C.-C., Lee, R.C.T., The weighted perfect domination problem and its variants (1996) Discrete Appl. Math., 66 (2), pp. 147-160 | ||
| 520 | 3 | |a A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exact algorithm for the problem. Furthermore, testing our algorithms also represented a challenge. Standard randomly generated graphs tend to contain a single perfect edge dominating solution, i.e., the trivial one, containing all edges in the graph. Accordingly, some quite elaborated procedures had to be devised to have access to more challenging instances. A total of 736 graphs were thus generated, all of them containing feasible solutions other than the trivial ones. Every graph giving rise to a weighted and a non weighted instance, all instances solved to proven optimality by two of the algorithms tested. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature. |l eng | |
| 536 | |a Article in Press | ||
| 593 | |a Departamento de Matemática, Universidade Federal Rural do Rio de Janeiro, Seropédica, Brazil | ||
| 593 | |a Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil | ||
| 593 | |a Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil | ||
| 690 | 1 | 0 | |a COMPUTATIONAL RESULTS |
| 690 | 1 | 0 | |a EXACT ALGORITHMS |
| 690 | 1 | 0 | |a INSTANCE GENERATION |
| 690 | 1 | 0 | |a PERFECT EDGE DOMINATION |
| 690 | 1 | 0 | |a OPTIMIZATION |
| 690 | 1 | 0 | |a COMPUTATIONAL RESULTS |
| 690 | 1 | 0 | |a DOMINATION PROBLEM |
| 690 | 1 | 0 | |a EXACT ALGORITHMS |
| 690 | 1 | 0 | |a FEASIBLE SOLUTION |
| 690 | 1 | 0 | |a INSTANCE GENERATION |
| 690 | 1 | 0 | |a MATHEMATICAL FORMULATION |
| 690 | 1 | 0 | |a OPTIMALITY |
| 690 | 1 | 0 | |a PERFECT EDGE DOMINATION |
| 690 | 1 | 0 | |a CONTROL ENGINEERING |
| 700 | 1 | |a Lin, M.C. | |
| 700 | 1 | |a Lucena, A. | |
| 700 | 1 | |a Maculan, N. | |
| 700 | 1 | |a Moyano, V.A. | |
| 700 | 1 | |a Szwarcfiter, J.L. | |
| 773 | 0 | |d Springer Verlag, 2018 |p Optim. Lett. |x 18624472 |t Optimization Letters | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85055332381&doi=10.1007%2fs11590-018-1335-x&partnerID=40&md5=83854708410f656589bb82a6f1d29baa |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s11590-018-1335-x |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_18624472_v_n_p_doForte |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18624472_v_n_p_doForte |y Registro en la Biblioteca Digital |
| 961 | |a paper_18624472_v_n_p_doForte |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 86233 | ||