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...

Descripción completa

Detalles Bibliográficos
Publicado: 2015
Materias:
Circular-Arc graphs
Efficient Domination
Perfect Domination
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p307_Lin
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p307_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v50_n_p307_Lin
record_format dspace
spelling paper:paper_15710653_v50_n_p307_Lin2023-06-08T16:24:30Z Efficient and Perfect domination on circular-arc graphs 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. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p307_Lin 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
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.
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
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p307_Lin
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p307_Lin
_version_ 1768544152453120000

Ejemplares similares