Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Lozin, V.; Moyano, V.A.; Szwarcfiter, J.L. "Perfect edge domination: hard and solvable cases" (2018) Annals of Operations Research. 264(1-2):287-305
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:

Let G be an undirected graph. An edge of Gdominates itself and all edges adjacent to it. A subset E′ of edges of G is an edge dominating set of G, if every edge of the graph is dominated by some edge of E′. We say that E′ is a perfect edge dominating set of G, if every edge not in E′ is dominated by exactly one edge of E′. The perfect edge dominating problem is to determine a least cardinality perfect edge dominating set of G. For this problem, we describe two NP-completeness proofs, for the classes of claw-free graphs of degree at most 3, and for bounded degree graphs, of maximum degree at most d≥ 3 and large girth. In contrast, we prove that the problem admits an O(n) time solution, for cubic claw-free graphs. In addition, we prove a complexity dichotomy theorem for the perfect edge domination problem, based on the results described in the paper. Finally, we describe a linear time algorithm for finding a minimum weight perfect edge dominating set of a P5-free graph. The algorithm is robust, in the sense that, given an arbitrary graph G, either it computes a minimum weight perfect edge dominating set of G, or it exhibits an induced subgraph of G, isomorphic to a P5. © 2017, Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Perfect edge domination: hard and solvable cases
Autor:Lin, M.C.; Lozin, V.; Moyano, V.A.; Szwarcfiter, J.L.
Filiación:Consejo Nacional de Investigaciones Científicas y Técnicas, Buenos Aires, Argentina
Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
University of Warwick, Coventry, United Kingdom
Instituto de Cálculo and Departamento de Matemática, Universidad de Buenos Aires, Buenos Aires, Argentina
I. Mat., COPPE and NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
Instituto Nacional de Metrologia, Qualidade e Tecnologia, Rio de Janeiro, Brazil
Palabras clave:Claw-free graphs; Complexity dichotomy; Cubic graphs; NP-completeness; Perfect edge domination
Año:2018
Volumen:264
Número:1-2
Página de inicio:287
Página de fin:305
DOI: http://dx.doi.org/10.1007/s10479-017-2664-3
Título revista:Annals of Operations Research
Título revista abreviado:Ann. Oper. Res.
ISSN:02545330
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v264_n1-2_p287_Lin

Referencias:

  • Bacsó, G., Tuza, Z., Dominating cliques in P5 -free graphs (1990) Periodica Mathemayica Hungarica, 21, pp. 303-308
  • Brandstadt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) Proceedings of the 23Rd International Symposium on Algorithms and Computation (ISAAC 2012), 7676, pp. 277-558. , Lecture Notes in Computer Science
  • Brandstadt, A., Mosca, R., Dominating induced matching for P 7 -free graphs in linear time (2011) Proceedings of the 22Nd International Symposium on Algorithms and Computation (ISAAC 2011), pp. 100-109. , Lecture Notes in Computer Science
  • Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C., Efficient edge domination in regular graphs (2008) Discrete Applied Mathematics, 156, pp. 3060-3065
  • Camby, E., Schaudt, O., (2014) A new characterization of Pk -free graphs, Graph-theoretic concepts in computer science—40th international workshop (WG 2014), pp. 129-138. , France, Revised Selected Papers
  • Cardoso, D.M., Koperlainen, N., Lozin, V.V., On the complexity of the induced matching problem in hereditary classes of graphs (2011) Discrete Applied Mathematics, 159, pp. 521-531
  • Georges, J.P., Halsey, M.D., Sanaulla, A.M., Whittlesey, M.A., Edge domination and graph structure (1990) Congressus Numerantium, 76, pp. 127-144
  • Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holnes, N.D., Efficient edge domination problems in graphs (1993) Information Processing Letters, 48, pp. 221-228
  • Hertz, A., Lozin, V., Ries, B., Zamaraev, V., de Werra, D., Dominating induced matchings in graphs containing no long claw (2015) Journal of Graph Theory, , accepted
  • Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., An O ∗ (1. 1939 n) time algorithm for minimum weighted dominating induced matching (2013) In Proceedings of the 24Th International Symposium on Algorithms and Computation (ISAAC 2013), 8283, pp. 558-567. , Hong Kong, Lecture Notes in Computer Science
  • Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., (2013) Exact Algorithms for Dominating Induced Matching
  • Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., Fast algorithms for some dominating induced matching problems (2014) Information Processing Letters, 114, pp. 524-528
  • Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., Efficient and perfect domination on circular-arc graphs (2015) In Proceedings of the VIII Latin-American Graphs, Algorithms and Optimization Symposium (LAGOS’ 2015), , Beberibe, Brazil, Electronic Notes in Discrete Mathematics (to appear)
  • Lin, M.C., Moyano, V., Rautenbach, D., Szwarcfiter, J.L., The maximum number of dominating induced matchings (2015) Journal of Graph Theory, 78, pp. 258-268
  • Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Applied Mathematics, 119, pp. 227-250
  • Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem in bipartite permutation graphs (1998) Discrete Applied Mathematics, 87, pp. 203-211
  • Xiao, M., Nagamochi, H., Exact algorithms for dominating induced matching based on graph partition (2015) Discrete Applied Mathematics, 190-191, pp. 147-162

Citas:

---------- APA ----------
Lin, M.C., Lozin, V., Moyano, V.A. & Szwarcfiter, J.L. (2018) . Perfect edge domination: hard and solvable cases. Annals of Operations Research, 264(1-2), 287-305.
http://dx.doi.org/10.1007/s10479-017-2664-3
---------- CHICAGO ----------
Lin, M.C., Lozin, V., Moyano, V.A., Szwarcfiter, J.L. "Perfect edge domination: hard and solvable cases" . Annals of Operations Research 264, no. 1-2 (2018) : 287-305.
http://dx.doi.org/10.1007/s10479-017-2664-3
---------- MLA ----------
Lin, M.C., Lozin, V., Moyano, V.A., Szwarcfiter, J.L. "Perfect edge domination: hard and solvable cases" . Annals of Operations Research, vol. 264, no. 1-2, 2018, pp. 287-305.
http://dx.doi.org/10.1007/s10479-017-2664-3
---------- VANCOUVER ----------
Lin, M.C., Lozin, V., Moyano, V.A., Szwarcfiter, J.L. Perfect edge domination: hard and solvable cases. Ann. Oper. Res. 2018;264(1-2):287-305.
http://dx.doi.org/10.1007/s10479-017-2664-3