Efficient and Perfect domination on circular-arc graphs | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.contributor.author | Lin, Min Chih | |
| dc.contributor.author | Mizrahi, Michel Jonathan | |
| dc.contributor.author | Szwarcfiter, Jayme L. | |
| dc.date.issued | 2015-12 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 1571-0653 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/59584 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 307-312 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Electronic Notes in Discrete Mathematics | es |
| dc.journal.volume | 50 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier | es |
| 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 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Efficient Domination | es |
| dc.subject | Perfect Domination | es |
| dc.subject | Circular-Arc Graphs | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Efficient and Perfect domination on circular-arc graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.e2f5cedd-3e5c-4f39-af90-35593e236357_A.pdf
- Tamaño:
- 174.14 KB
- Formato:
- Adobe Portable Document Format