Dra. Gabriela Argiroffo
garua@fceia.unr.edu.ar
Numerosas aplicaciones pueden ser modeladas como problemas de dominación en grafos. En efecto, a partir del concepto de dominación se modelan, entre otros, problemas de locación de servicios. Habitualmente, cada aplicación específica impone restricciones adicionales a los conjuntos dominantes, surgiendo de esta manera diferentes variaciones del problema.
El problema de dominación total en un grafo G=(V,E) es el problema de hallar un subconjunto de vértices D, de cardinal mínimo, tal que todo vértice de G tenga al menos un vecino en D o, equivalentemente, hallar una función f de V en {0,1} de peso mínimo y que satisfaga que, para todo i de V, (1) sum_{j in N(i)}f(j)>=1, donde N(i) es el conjunto de vecinos de i.
La mayoría de estas variaciones del problema son NP-completos. Sin embargo, el enfoque en términos de grafos ha sido de gran importancia para su estudio y ha contribuido al diseño y mejora de algoritmos específicos de resolución. En este proyecto nos enfocaremos en las variaciones del problema que se detallan a continuación, introducidos en Haynes, Hedetniemi y Slater (1999a,b).
El problema de k-tupla dominante total en un grafo de la siguiente manera: dado k natural, se pretende hallar una función f de V en {0,1} de peso mínimo y tal que para todo i de V, (2) sum_{j in N(i)}f(j)>=k.
Otra variación puede formularse como un problema de {k}-dominación total en un grafo: dado k natural se pretende hallar una función f de V en {0,1,...,k} de peso mínimo y que satisfaga (2). Dado un entero no negativo k, se pueden formular los problemas de decisión Problema de k-upla dominante total (k-DOM-T) y Problema de {k}-dominación total ({k}-DOM-T).
Recientemente, en Lan y Chang (2014), se generaliza la noción de k-upla dominante total a través de la dominación total etiquetada (problema de L-dominación total): sean un grafo G y una función de etiquetado M que asigna M(i)=(t(i),k(i)) a cada vértice i de G, donde t(i) está en {F,R} y k(i) es un entero no negativo. Una función de M-dominación es f, de V(G) en {0,1} tal que:
si t(i) es R, f(i)=1 y (3) sum_{j in N(i)}f(j) >= k(i) para todo i.
Análogamente, se considera el Problema de L-dominación total (L-DOM-T).
La tarea de desarrollo de este proyecto se enmarcará en el estudio de problemas abiertos referidos a estas variaciones del problema de dominación total clásico, haciendo uso de técnicas y herramientas que proporciona la teoría de grafos.
