Navegar

Colección

Datos Estadísticas

Artículo

do Forte, V.L.; Lin, M.C.; Lucena, A.; Maculan, N.; Moyano, V.A.; Szwarcfiter, J.L. "Modelling and solving the perfect edge domination problem" (2018) Optimization Letters
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Modelling and solving the perfect edge domination problem
Autor:do Forte, V.L.; Lin, M.C.; Lucena, A.; Maculan, N.; Moyano, V.A.; Szwarcfiter, J.L.
Filiación:Departamento de Matemática, Universidade Federal Rural do Rio de Janeiro, Seropédica, Brazil
Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil
Palabras clave:Computational results; Exact algorithms; Instance generation; Perfect edge domination; Optimization; Computational results; Domination problem; Exact algorithms; Feasible solution; Instance generation; Mathematical formulation; Optimality; Perfect edge domination; Control engineering
Año:2018
DOI: http://dx.doi.org/10.1007/s11590-018-1335-x
Título revista:Optimization Letters
Título revista abreviado:Optim. Lett.
ISSN:18624472
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18624472_v_n_p_doForte

Referencias:

  • 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
  • Biggs, N., Perfect codes in graphs (1973) J. Comb. Theory Ser. B, 15 (3), pp. 289-296
  • Bodur, M., Ekim, T., Taskin, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem (2013) Networks, 62 (4), pp. 273-287
  • Borndörfer, R., (1998) Aspects of Set Packing, Partitioning, and Covering, , Ph.D. thesis
  • 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
  • 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
  • Brandstädt, A., Mosca, R., (2011) Dominating Induced Matchings for P 7 -Free Graphs in Linear Time, , CoRR
  • Brandstädt, A., Mosca, R., Finding dominating induced matchings in p 8 -free graphs in polynomial time (2017) Algorithmica, 77 (4), pp. 1283-1302
  • 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
  • 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
  • Chang, G.J., Hwang, S., The edge domination problem (1995) Discuss. Math. Graph Theory, 15 (1), pp. 51-57
  • 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
  • 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
  • Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D., (2015) Dominating Induced Matchings in Graphs Containing No Long Claw, , CoRR
  • Horton, D.J., Kilakos, K., Minimum edge dominating sets (1993) SIAM J. Discrete Math., 6 (3), pp. 375-387
  • Horton, J.D., Bower, I.Z., Symmetric y-graphs and h-graphs (1991) J. Comb. Theory Ser. B, 53, pp. 114-129
  • (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
  • 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
  • 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
  • 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
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Exact algorithms for minimum weighted dominating induced matching (2017) Algorithmica, 77 (3), pp. 642-660
  • Liu, C.L., (1968) Introduction to Combinatorial Mathematics, , McGraw-Hill, New York
  • 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
  • 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
  • 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
  • Richey, M.B., Parker, R.G., Minimum-maximal matching in series–parallel graphs (1988) Eur. J. Oper. Res., 33 (1), pp. 98-105
  • 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
  • Taskin, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem (2012) Optim. Lett., 6 (6), pp. 1161-1171
  • Weichsel, P.M., Distance regular subgraphs of a cube (1992) Discrete Math., 109 (1-3), pp. 297-306
  • Weichsel, P.M., Dominating sets in n-cubes (1994) J. Graph Theory, 18 (5), pp. 479-488
  • Xiao, M., Nagamochi, H., Exact algorithms for dominating induced matching based on graph partition (2015) Discrete Appl. Math., 190-191, pp. 147-162
  • Yannakakis, M., Gavril, F., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372
  • Yen, C.-C., Lee, R.C.T., The weighted perfect domination problem and its variants (1996) Discrete Appl. Math., 66 (2), pp. 147-160

Citas:

---------- APA ----------
do Forte, V.L., Lin, M.C., Lucena, A., Maculan, N., Moyano, V.A. & Szwarcfiter, J.L. (2018) . Modelling and solving the perfect edge domination problem. Optimization Letters.
http://dx.doi.org/10.1007/s11590-018-1335-x
---------- CHICAGO ----------
do Forte, V.L., Lin, M.C., Lucena, A., Maculan, N., Moyano, V.A., Szwarcfiter, J.L. "Modelling and solving the perfect edge domination problem" . Optimization Letters (2018).
http://dx.doi.org/10.1007/s11590-018-1335-x
---------- MLA ----------
do Forte, V.L., Lin, M.C., Lucena, A., Maculan, N., Moyano, V.A., Szwarcfiter, J.L. "Modelling and solving the perfect edge domination problem" . Optimization Letters, 2018.
http://dx.doi.org/10.1007/s11590-018-1335-x
---------- VANCOUVER ----------
do Forte, V.L., Lin, M.C., Lucena, A., Maculan, N., Moyano, V.A., Szwarcfiter, J.L. Modelling and solving the perfect edge domination problem. Optim. Lett. 2018.
http://dx.doi.org/10.1007/s11590-018-1335-x