Perfect edge domination: hard and solvable cases
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Springer New York LLC
2018
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 08199caa a22007337a 4500 | ||
|---|---|---|---|
| 001 | PAPER-25210 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205713.0 | ||
| 008 | 190410s2018 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85030682118 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Lin, M.C. | |
| 245 | 1 | 0 | |a Perfect edge domination: hard and solvable cases |
| 260 | |b Springer New York LLC |c 2018 | ||
| 270 | 1 | 0 | |m Lin, M.C.; Consejo Nacional de Investigaciones Científicas y TécnicasArgentina; email: oscarlin@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Bacsó, G., Tuza, Z., Dominating cliques in P5 -free graphs (1990) Periodica Mathemayica Hungarica, 21, pp. 303-308 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Georges, J.P., Halsey, M.D., Sanaulla, A.M., Whittlesey, M.A., Edge domination and graph structure (1990) Congressus Numerantium, 76, pp. 127-144 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., (2013) Exact Algorithms for Dominating Induced Matching | ||
| 504 | |a Lin, M.C., Mizrahi, M., Szwarcfiter, J.L., Fast algorithms for some dominating induced matching problems (2014) Information Processing Letters, 114, pp. 524-528 | ||
| 504 | |a 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) | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Xiao, M., Nagamochi, H., Exact algorithms for dominating induced matching based on graph partition (2015) Discrete Applied Mathematics, 190-191, pp. 147-162 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Consejo Nacional de Investigaciones Científicas y Técnicas, CONICET | ||
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, CAPES | ||
| 536 | |a Detalles de la financiación: 2013-2205 | ||
| 536 | |a Detalles de la financiación: Russian Science Foundation, RSF, 17-11-01336 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, UBACyT, 20020130100800BA, 20020120100058 | ||
| 536 | |a Detalles de la financiación: Consejo Nacional de Investigaciones Científicas y Técnicas, Buenos Aires, Argentina | ||
| 536 | |a Detalles de la financiación: Acknowledgements We appreciate the comments of an anonymous reviewer, which significantly helped us improving the presentation and clarity of this work. Min Chih Lin and Veronica A. Moyano were partially supported by UBACyT Grants 20020120100058 and 20020130100800BA, and PICT ANPCyT Grant 2013-2205. Vadim Lozin acknowledges support of the Russian Science Foundation, Grant 17-11-01336. Jayme L. Szwarfiter was partially supported by CNPq and CAPES, research agencies. | ||
| 593 | |a Consejo Nacional de Investigaciones Científicas y Técnicas, Buenos Aires, Argentina | ||
| 593 | |a Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a University of Warwick, Coventry, United Kingdom | ||
| 593 | |a Instituto de Cálculo and Departamento de Matemática, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a I. Mat., COPPE and NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil | ||
| 593 | |a Instituto Nacional de Metrologia, Qualidade e Tecnologia, Rio de Janeiro, Brazil | ||
| 690 | 1 | 0 | |a CLAW-FREE GRAPHS |
| 690 | 1 | 0 | |a COMPLEXITY DICHOTOMY |
| 690 | 1 | 0 | |a CUBIC GRAPHS |
| 690 | 1 | 0 | |a NP-COMPLETENESS |
| 690 | 1 | 0 | |a PERFECT EDGE DOMINATION |
| 700 | 1 | |a Lozin, V. | |
| 700 | 1 | |a Moyano, V.A. | |
| 700 | 1 | |a Szwarcfiter, J.L. | |
| 773 | 0 | |d Springer New York LLC, 2018 |g v. 264 |h pp. 287-305 |k n. 1-2 |p Ann. Oper. Res. |x 02545330 |t Annals of Operations Research | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030682118&doi=10.1007%2fs10479-017-2664-3&partnerID=40&md5=725f2b2cc0f089d2d4d3a52828f82853 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10479-017-2664-3 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_02545330_v264_n1-2_p287_Lin |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v264_n1-2_p287_Lin |y Registro en la Biblioteca Digital |
| 961 | |a paper_02545330_v264_n1-2_p287_Lin |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 86163 | ||