Mostrar el registro sencillo del ítem
dc.contributor.author
Leoni, Valeria Alejandra
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Fernández, Lara Iliana
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2024-01-10T13:13:52Z
dc.date.issued
2023-07
dc.identifier.citation
Leoni, Valeria Alejandra; Fernández, Lara Iliana; New complexity results on Roman {2}-domination; EDP Sciences; Rairo - Recherche Operationnelle (operations Research); 57; 4; 7-2023; 1905-1912
dc.identifier.issn
0399-0559
dc.identifier.uri
http://hdl.handle.net/11336/223174
dc.description.abstract
The study of a variant of Roman domination was initiated by Chellali et al. [Discrete Appl. Math. 204 (2016) 22- 28]. Given a graph G with vertex set V, a Roman {2}-dominating function f: V → {0, 1, 2} has the property that for every vertex v ϵ V with f(v) = 0, either there exists a vertex u adjacent to v with f(u) = 2, or at least two vertices x, y adjacent to v with f(x) = f(y) = 1. The weight of a Roman {2}-dominating function is the value f(V) = ∑ vϵ V f(v). The minimum weight of a Roman {2}-dominating function is called the Roman {2}-domination number and is denoted by γ{R2}(G). In this work we find several NP-complete instances of the Roman {2}-domination problem: chordal graphs, bipartite planar graphs, chordal bipartite graphs, bipartite with maximum degree 3 graphs, among others. A result by Chellali et al. [Discrete Appl. Math. 204 (2016) 22- 28] shows that γ{R2}(G) and the 2-rainbow domination number of G coincide when G is a tree, and thus, the linear time algorithm for k-rainbow domination due to Brešar et al. [Taiwan J. Math. 12 (2008) 213- 225] can be followed to compute γ{R2}(G). In this work we develop an efficient algorithm that is independent of k-rainbow domination and computes the Roman {2}-domination number on a subclass of trees called caterpillars.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
EDP Sciences
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CATERPILLAR
dc.subject
DECOMPOSITION
dc.subject
EFFICIENT ALGORITHM
dc.subject
NP-COMPLETE
dc.subject.classification
Otras Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
New complexity results on Roman {2}-domination
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2024-01-09T15:01:09Z
dc.journal.volume
57
dc.journal.number
4
dc.journal.pagination
1905-1912
dc.journal.pais
Francia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Paris
dc.description.fil
Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentina
dc.description.fil
Fil: Fernández, Lara Iliana. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.journal.title
Rairo - Recherche Operationnelle (operations Research)
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1051/ro/2023049
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.rairo-ro.org/articles/ro/abs/2023/04/ro220776/ro220776.html
Archivos asociados