Sesión Matemática Discreta

Diciembre 15, 11:40 ~ 12:00

$k$-dominación y $k$-dominación total en grafos de intervalos propios.

LOPEZ PUJATO, M. Inés

{Muchos problemas de interés práctico y teórico requieren cubrir objetos, como lo son los problemas de locación de servicios. Por ejemplo, uno puede requerir cubrir con el menor número posible de sensores cierta zona para ser monitoreada, teniendo en cuenta que pocos sensores cercanos a un determinado lugar pueden no realizar un monitoreo completo. \'{E}stos pueden ser modelados como ciertas variaciones de dominación en grafos. Para un entero $k \geq 1$ y un grafo $G$, la $k$-dominación total fue introducida en $[6]$ y estudiada por ej. en $[7]$. Por otra parte, la $k$-dominación fue introducida en $[5]$ y estudiada por ej. en $[4]$. Un conjunto $S$ de vértices de $G$ es $k$-dominante total ($k$-dominante) si todo vértice de $G$ (todo v\'{e}rtice de $G$ que no está en $S$) tiene al menos $k$ "`vecinos"' en $S$. Para cada $k$ fijo, el problema de hallar el tamaño mínimo entre todos los conjuntos $k$-dominantes totales ($k$-dominantes) en $G$ es NP-difícil en grafos generales. %Cuando abordamos problemas NP-difíciles, es importante la determinación de familias de grafos donde los mismos pueden ser resueltos en tiempo polinomial. Para la $k$-dominación (total) y la clase de grafos de intervalos, el caso $k = 1$ fue estudiado en $[2]$ ($[1]$). Se tiene interés en estos grafos porque modelan situaciones reales de intersecciones de intervalos (de tiempo, por ej.) en la recta real. En el reciente trabajo $[3]$, a partir de que estos problemas pueden ser escritos en la lógica LC-VSVP, se puede deducir su polinomialidad para todo valor de $k$ en los grafos de intervalos ya que \'{e}stos tienen min-width acotado. Sin embargo, el orden de convergencia del algoritmo correspondiente puede reducirse notoriamente en esta clase. Usando fuertemente la estructura de estos grafos e inspirados en $[1]$, diseñamos un algoritmo específico para todo $k$ cuyo orden de convergencia es igual a la raíz cuadrada del orden original, a partir de una reducción a la búsqueda de un camino más corto en un digrafo con peso en los arcos. \begin{thebibliography}{10}\label{bibliography} %\bibitem{ALT2016+} Argiroffo, G., Leoni, V., Torres, P.; Complexity of $k$-tuple total domination and total $\{k\}$-domination in some subclasses of bipartite graphs, Submmitted, 2017. \bibitem{Bertossi} Bertossi, A., Total domination in interval graphs, Inform. Process. Lett., Information Processing Letters, 23, 1986, 3, 131--134. %\bibitem{MR2974046} Chellali, M., Nacéra M., Trees with equal 2-domination and 2-independence numbers. Math. Graph Theory, Discussiones Mathematicae. Graph Theory, 32, 2012, 2, 263--270. \bibitem{Booth} K.S. Booth and J. H. Johnson, Dominating sets in chordal graphs, SIAM J. Comput. 11, 1982, 191--199. \bibitem{Kang} D. Y. Kang, O. Kwon, T. J.F. Strømme, Jan Arne Telle, A width parameter useful for chordal and co-comparability graphs, 2017, https:/arxiv.org/abs/1606.08087. %\bibitem{MR2776174} DeLaVi\~na, Ermelinda and Goddard, Wayne and Henning, Michael A. and Pepper, Ryan and Vaughan, Emil R., Bounds on the {$k$}-domination number of a graph, Appl. Math. Lett., Applied Mathematics Letters. An International Journal of Rapid Publication, 24, 2011, 6, 996--998. \bibitem{MR2370182} Favaron, O., Hansberg, A., Volkmann, L., On {$k$}-domination and minimum degree in graphs, J. Graph Theory, Journal of Graph Theory, 57, 2008, 1, 33--40. \bibitem{MR812671} Fink, J. F. and Jacobson, M. S.,{$n$}-domination in graphs, Wiley-Intersci. Publ, 283--300, Wiley, New York, 1985. %\bibitem{MR3043099} Hansberg, Adriana and Pepper, Ryan, On {$k$}-domination and {$j$}-independence in graphs, Discrete Appl. Math., %Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 161, 2013, 10-11, 1472--1480. \bibitem{MR2607047} Henning, M.A., Kazemi, A. P., {$k$}-tuple total domination in graphs, Discrete Appl. Math., 158, 2010, 9, 1006--1011. %\bibitem{MR2974027} Kazemi, Adel P., On the total {$k$}-domination number of graphs, Discuss. Math. Graph Theory, Discussiones Mathematicae. Graph Theory, 32, 2012, 3, 419--426. %\bibitem{MR3043104} Lan, James K. and Chang, Gerard Jennhwa, Algorithmic aspects of the {$k$}-domination problem in graphs, Discrete Appl. Math., Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 161, 2013, 10-11, 1513--1520. %\bibitem{MR3215459} Lan, James K. and Chang, Gerard Jennhwa, On the algorithmic complexity of {$k$}-tuple total domination, Discrete Appl. Math., Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 174, 2014, 81--91. \bibitem{MR2960327} Pradhan, D., Algorithmic aspects of {$k$}-tuple total domination in graphs, Inform. Process. Lett., Information Processing Letters, 112, 2012, 21, 816--822. \end{thebibliography} }

Autores: LOPEZ PUJATO, M. Inés / Leoni, Valeria / Milanic, Martin / Chiarelli, Nina / Hartinger, Tatiana.