Efficient and Perfect domination on circular-arc graphs
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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p307_Lin |
| Aporte de: |
| id |
todo:paper_15710653_v50_n_p307_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15710653_v50_n_p307_Lin2023-10-03T16:27:09Z Efficient and Perfect domination on circular-arc graphs Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. Circular-Arc graphs Efficient Domination Perfect Domination 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. © 2015. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p307_Lin |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Circular-Arc graphs Efficient Domination Perfect Domination |
| spellingShingle |
Circular-Arc graphs Efficient Domination Perfect Domination Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. Efficient and Perfect domination on circular-arc graphs |
| topic_facet |
Circular-Arc graphs Efficient Domination Perfect Domination |
| description |
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. © 2015. |
| format |
JOUR |
| author |
Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. |
| author_facet |
Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. |
| author_sort |
Lin, M.C. |
| title |
Efficient and Perfect domination on circular-arc graphs |
| title_short |
Efficient and Perfect domination on circular-arc graphs |
| title_full |
Efficient and Perfect domination on circular-arc graphs |
| title_fullStr |
Efficient and Perfect domination on circular-arc graphs |
| title_full_unstemmed |
Efficient and Perfect domination on circular-arc graphs |
| title_sort |
efficient and perfect domination on circular-arc graphs |
| url |
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p307_Lin |
| work_keys_str_mv |
AT linmc efficientandperfectdominationoncirculararcgraphs AT mizrahimj efficientandperfectdominationoncirculararcgraphs AT szwarcfiterjl efficientandperfectdominationoncirculararcgraphs |
| _version_ |
1807324139755667456 |