000098159 001__ 98159 000098159 005__ 20210118122905.0 000098159 037__ $$aTAZ-TFG-2020-1911 000098159 041__ $$aspa 000098159 1001_ $$aDíez Corral, Javier 000098159 24200 $$aConnected dominating set of a graph. 000098159 24500 $$aConjunto dominante conexo de un grafo. 000098159 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2020 000098159 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000098159 520__ $$aEl objetivo de este trabajo es el estudio del problema del cálculo de un conjunto dominante conexo de cardinal de tamaño mínimo en un grafo no dirigido. La principal aplicación de este problema se halla en la optimización del rendimiento de redes de comunicaciones. El tema central del trabajo estará dedicado a la demostración de que el problema pertenece a la clase de complejidad computacional NP-Completo así como a la descripción y análisis de tres algoritmos que permiten obtener una solución aproximada al problema en tiempo polinómico. Se incluye también un breve estudio del problema en triangulaciones planas y casi-triangulaciones.<br /><br /> 000098159 521__ $$aGraduado en Matemáticas 000098159 540__ $$aDerechos regulados por licencia Creative Commons 000098159 700__ $$aGarcía Olaverri, Alfredo$$edir. 000098159 7102_ $$aUniversidad de Zaragoza$$bMétodos Estadísticos$$c 000098159 8560_ $$f728695@unizar.es 000098159 8564_ $$s568328$$uhttps://zaguan.unizar.es/record/98159/files/TAZ-TFG-2020-1911.pdf$$yMemoria (spa) 000098159 909CO $$ooai:zaguan.unizar.es:98159$$pdriver$$ptrabajos-fin-grado 000098159 950__ $$a 000098159 951__ $$adeposita:2021-01-18 000098159 980__ $$aTAZ$$bTFG$$cCIEN 000098159 999__ $$a20200624194028.CREATION_DATE