Mostrar el registro sencillo del ítem
dc.contributor.author
Lin, Min Chih
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Mizrahi, Michel Jonathan
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Szwarcfiter, Jayme L.
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2018-09-13T18:52:55Z
dc.date.issued
2015-12
dc.identifier.citation
Lin, Min Chih; Mizrahi, Michel Jonathan; Szwarcfiter, Jayme L.; Efficient and Perfect domination on circular-arc graphs; Elsevier; Electronic Notes in Discrete Mathematics; 50; 12-2015; 307-312
dc.identifier.issn
1571-0653
dc.identifier.uri
http://hdl.handle.net/11336/59584
dc.description.abstract
Given a graph G = (V,E), a perfect dominating set is a subset of vertices V ⊆ V (G) such that each vertex v ∈ V (G) \ V is dominated by exactly one vertex v ∈ V . An efficient dominating set is a perfect dominating set V where V is also an independent set. These problems are usually posed in terms of edges instead of vertices. Both problems, either for the vertex or edge variant, remains NP-Hard, even when restricted to certain graphs families. We study both variants of the problems for the circular-arc graphs, and show efficient algorithms for all of them.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
![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-nd/2.5/ar/
dc.subject
Efficient Domination
dc.subject
Perfect Domination
dc.subject
Circular-Arc Graphs
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![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
Efficient and Perfect domination on circular-arc graphs
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
2018-09-13T13:14:06Z
dc.journal.volume
50
dc.journal.pagination
307-312
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Mizrahi, Michel Jonathan. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil
dc.journal.title
Electronic Notes in Discrete Mathematics
![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/https://doi.org/10.1016/j.endm.2015.07.051
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065315002061
Archivos asociados