Mostrar el registro sencillo del objeto digital

dc.contributor Valdovinos Rosas, Rosa María
dc.contributor Montes Venegas, Héctor Alejandro
dc.contributor.advisor MARCIAL ROMERO, JOSE RAYMUNDO; 39478
dc.contributor.author GUZMAN PONCE, ANGELICA
dc.creator GUZMAN PONCE, ANGELICA; 702275
dc.date.accessioned 2018-03-15T09:28:18Z
dc.date.available 2018-03-15T09:28:18Z
dc.date.issued 2017-10-09
dc.identifier.uri http://hdl.handle.net/20.500.11799/80038
dc.description El problema del coloreo de gráficas por su importancia se ha tratado de solucionar por diferentes algoritmos, entre los más usados se encuentran los heurísticos, los cuales aproximan la solución, además existen diferentes metodologías de solución. En particular, el presente trabajo de Tesis se ha centrado en tres algoritmos heurísticos, el algoritmo greedy de JGraphT, el algoritmo determinista propuesto por Guzmán et al. y las propuestas híbridas de combinar un algoritmo determinista con un algoritmo genético. Derivado de los resultados obtenidos se puede concluir que en términos de n umero de colores las propuestas de Guzmán et al.(Apéndice A) y la que se presenta como trabajo final de tesis son competitivas, debido a que, el promedio de colores obtenidos en 20 ejecuciones, los resultados obtenidos por la propuesta híbrida de esta tesis, son mejores en gran medida que los obtenidos por Guzmán et al. debido a que el número de colores no está disperso con respecto al promedio obtenido, esto se observa en la desviación estándar obtenida para cada prueba. Adicionalmente, de los resultados de coloreo obtenidos por JGraphT el 62.5% excede el coloreo de una a diez unidades de color, mientras que la propuesta de esta Tesis en s olo 45.83% de las instancias el coloreo excede de una a cinco unidades de color, mientras que para Guzmán et al. en un 58.33% el coloreo obtenido excede de una a seis unidades de color. Los resultados obtenidos en esta investigación y concluidos como los que mantienen una mejor aproximación al coloreo, se deben a la implementación de la Fase de regeneración, la cual favoreció en la mayoría de las instancias, que de la gráfica conocida como residual, a que la aproximación al coloreo se cumpliera con el número de colores restantes, es decir el número k conocido como el mejor coloreo obtenido hasta el momento, se le resta el número de MISes extraídos de la primera fase, debido a que los MISes de la fase de extracción son considerados de la completa, dejando una gráfica residual densa, la cual complica que el coloreo sea propio con k-MISes. Por otro lado, de los análisis realizados en la Sección 4 se encuentra el de tiempo de ejecución, donde se muestra el tiempo en segundos que tardó cada algoritmo en obtener una aproximación, de esto se puede concluir que en términos de tiempo de ejecución el algoritmo híbrido propuesto, toma un mayor tiempo de ejecución en comparación con el resto de los algoritmos comparados, debido a que en la fase de regeneración se considera un número de iteraciones para reconstruir un MIS, así como también el volver a implementar la fase completa de coloreo, dentro de la cual el tiempo que se toma en ejecutar la búsqueda Tabú incrementa el tiempo de ejecución. Sin embargo, ya que el objetivo general fue mejorar la aproximación al coloreo, se considera que se cumplió el objetivo y se verificó la hipótesis propuesta. es
dc.description.abstract Dada una gráfíca no dirigida G = (V;E) con un conjunto de vértices V y un conjunto de aristas E, el problema del coloreo de gráfícacas consiste en particionar todos los vértices de V en el mínimo número K de conjuntos (colores), con la característica de que cada par de vértices en un conjunto no compartan arista. El problema de coloreo se ha estudiado desde 3 perspectivas, la primera es el problema original, encontrar el mínimo número de colores con los cuales una gráfíca puede ser coloreado, la segunda trata de decidir si una gráfíca es k colorable, mientras que la última, aproxima el coloreo con respecto al mejor valor reportado en la literatura (ya que puede no conocerse el mínimo). Diversas propuestas de algoritmos se han desarrollado de manera exacta o heurísticas. En esta Tesis se propone un algoritmo de tipo heurístico resultado de la combinación de un algoritmo determinista y un algoritmo evolutivo para aproximar el coloreo de gráficas con respecto al mejor valor reportado en la literatura. El algoritmo propuesto se evalúa con un conjunto de gráficas propuestas en la literatura. Los resultados obtenidos validan la viabilidad de la propuesta con respecto a otros algoritmos reportados en la literatura. es
dc.description.sponsorship Conacyt: 702275/584432 es
dc.language.iso spa es
dc.publisher Universidad Autónoma del Estado de México es
dc.rights openAccess es
dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/4.0
dc.subject coloreo de graficas es
dc.subject conjuntos maximales independientes es
dc.subject teoría de graficas es
dc.subject busqueda tabú es
dc.subject algoritmos genéticos es
dc.subject heuristicas es
dc.subject.classification INGENIERÍA Y TECNOLOGÍA
dc.title Diseño de un algoritmo para aproximar el coloreo de una gráfica mediante conjuntos maximales independientes es
dc.type Tesis de Maestría es
dc.provenance Científica es
dc.road Dorada es
dc.organismo Ingeniería es
dc.ambito Internacional es
dc.cve.CenCos 20501 es
dc.cve.progEstudios 679 es
dc.modalidad Tesis es
dc.audience students
dc.audience researchers
dc.type.conacyt masterThesis
dc.identificator 7


Ficheros en el objeto digital

Este ítem aparece en la(s) siguiente(s) colección(ones)

Visualización del Documento

  • Título
  • Diseño de un algoritmo para aproximar el coloreo de una gráfica mediante conjuntos maximales independientes
  • Autor
  • GUZMAN PONCE, ANGELICA
  • Colaborador
  • Valdovinos Rosas, Rosa María
  • Montes Venegas, Héctor Alejandro
  • Fecha de publicación
  • 2017-10-09
  • Editor
  • Universidad Autónoma del Estado de México
  • Tipo de documento
  • Tesis de Maestría
  • Palabras clave
  • coloreo de graficas
  • conjuntos maximales independientes
  • teoría de graficas
  • busqueda tabú
  • algoritmos genéticos
  • heuristicas
  • Los documentos depositados en el Repositorio Institucional de la Universidad Autónoma del Estado de México se encuentran a disposición en Acceso Abierto bajo la licencia Creative Commons: Atribución-NoComercial-SinDerivar 4.0 Internacional (CC BY-NC-ND 4.0)

Mostrar el registro sencillo del objeto digital

openAccess Excepto si se señala otra cosa, la licencia del ítem se describe cómo openAccess

Buscar en RI


Buscar en RI

Usuario

Estadísticas