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. © 2015.
Registro:
Documento: |
Artículo
|
Título: | Efficient and Perfect domination on circular-arc graphs |
Autor: | Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L. |
Filiación: | CONICET, Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina Inst de Matemática, COPPE and NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
|
Palabras clave: | Circular-Arc graphs; Efficient Domination; Perfect Domination |
Año: | 2015
|
Volumen: | 50
|
Página de inicio: | 307
|
Página de fin: | 312
|
DOI: |
http://dx.doi.org/10.1016/j.endm.2015.07.051 |
Título revista: | Electronic Notes in Discrete Mathematics
|
Título revista abreviado: | Electron. Notes Discrete Math.
|
ISSN: | 15710653
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p307_Lin |
Referencias:
- Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) LNCS, 7676, pp. 267-277. , ISAAC'12 International Symposium on Algorithms and Computation
- Chang, M., Efficient algorithms for the domination problems on interval and circular-arc graphs (1998) SIAM J. Comput., 27, pp. 1671-1694
- Chang, M., Liu, Y., Polynomial algorithms for weighted perfect domination problems on interval and circular-arc graphs (1994) J. Inf. Sci. Eng., 11, pp. 549-568
- Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discrete Appl. Math., 154, pp. 1783-1790
- Lin, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L., On cliques of Helly circular-arc graphs (2008) Electron. Notes Discrete Math., 30, pp. 117-122
- Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Efficient and Perfect domination on circular-arc graphs (2015) CoRR, , abs/1502.01523
- Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Exact algorithms for dominating induced matchings (2013) CoRR, , abs/1301.7602
- Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Fast algorithms for some dominating induced matching problems (2014) Inf. Process. Lett., 114, pp. 524-528
- Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Appl. Math., 119, pp. 227-250
- McConnell, R.M., (2003) Linear-Time Recognition of Circular-Arc Graphs Algorithmica, 37, pp. 93-147
- Spinrad, J., Efficient Graph Representations: The Fields Institute for Research in Mathematical Sciences (2003) Fields Institute monographs, , American Mathematical Soc
Citas:
---------- APA ----------
Lin, M.C., Mizrahi, M.J. & Szwarcfiter, J.L.
(2015)
. Efficient and Perfect domination on circular-arc graphs. Electronic Notes in Discrete Mathematics, 50, 307-312.
http://dx.doi.org/10.1016/j.endm.2015.07.051---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.
"Efficient and Perfect domination on circular-arc graphs"
. Electronic Notes in Discrete Mathematics 50
(2015) : 307-312.
http://dx.doi.org/10.1016/j.endm.2015.07.051---------- MLA ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.
"Efficient and Perfect domination on circular-arc graphs"
. Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 307-312.
http://dx.doi.org/10.1016/j.endm.2015.07.051---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. Efficient and Perfect domination on circular-arc graphs. Electron. Notes Discrete Math. 2015;50:307-312.
http://dx.doi.org/10.1016/j.endm.2015.07.051