000127235 001__ 127235 000127235 005__ 20230907110835.0 000127235 037__ $$aTAZ-TFG-2023-2761 000127235 041__ $$aspa 000127235 1001_ $$aMairal Buera, Claudia 000127235 24200 $$aMaximum independent set in a graph. 000127235 24500 $$aEl problema del máximo conjunto independiente en un grafo. 000127235 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2023 000127235 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000127235 520__ $$aEn teoría de grafos, un conjunto independiente es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. El propósito principal de este Trabajo Fin de Grado reside en el estudio del problema de hallar un conjunto independiente máximo en un grafo y en su complejidad computacional. Este problema es equivalente a otros problemas básicos de grafos (como el de hallar un máximo clique o recubrimiento de vértices mínimo), y es un problema de la clase NP-Hard que aparece de forma natural en muchas aplicaciones reales. <br />El trabajo incluye las siguientes partes: <br />- Una descripción del problema, problemas de grafos equivalentes y relacionados. Aplicaciones.<br />- Complejidad del problema: introducción a la complejidad computacional y demostración de que el problema es NP-Hard.<br />- Algoritmos exactos y algoritmos heurísticos para hallar un conjunto independiente óptimo. Formulación del problema como un PLE. El problema del máximo conjunto independiente en grafos de intervalo y los problemas de Scheduling.<br /><br /> 000127235 521__ $$aGraduado en Matemáticas 000127235 540__ $$aDerechos regulados por licencia Creative Commons 000127235 700__ $$aGarcía Olaverri, Alfredo$$edir. 000127235 7102_ $$aUniversidad de Zaragoza$$bMétodos Estadísticos$$c 000127235 8560_ $$f795115@unizar.es 000127235 8564_ $$s635623$$uhttps://zaguan.unizar.es/record/127235/files/TAZ-TFG-2023-2761.pdf$$yMemoria (spa) 000127235 909CO $$ooai:zaguan.unizar.es:127235$$pdriver$$ptrabajos-fin-grado 000127235 950__ $$a 000127235 951__ $$adeposita:2023-09-07 000127235 980__ $$aTAZ$$bTFG$$cCIEN 000127235 999__ $$a20230614132644.CREATION_DATE