Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L. "Efficient and Perfect domination on circular-arc graphs" (2015) Electronic Notes in Discrete Mathematics. 50:307-312
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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