{"id":2670,"date":"2022-08-13T19:40:39","date_gmt":"2022-08-13T19:40:39","guid":{"rendered":"https:\/\/pcyti.izt.uam.mx\/?p=2670"},"modified":"2022-08-13T19:40:39","modified_gmt":"2022-08-13T19:40:39","slug":"estudio-comparativo-de-algoritmos-de-solucion-para-el-problema-de-coloracion-de-graficas-suaves","status":"publish","type":"post","link":"https:\/\/pcyti.izt.uam.mx\/?p=2670","title":{"rendered":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves."},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/wp-content\/uploads\/06_PLV.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">&nbsp;Descargar versi\u00f3n PDF<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Profesores<\/strong>:&nbsp;<a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/?page_id=198&amp;SingleProduct=195\">Dr. Pedro Lara Vel\u00e1zquez<\/a>&nbsp;y&nbsp;<a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/?page_id=198&amp;SingleProduct=194\">Dr. Miguel \u00c1ngel Guti\u00e9rrez Andrade<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Resumen<\/strong>:&nbsp; La coloraci\u00f3n de gr\u00e1ficas suaves es una generalizaci\u00f3n del problema de coloraci\u00f3n en el que se busca encontrar una coloraci\u00f3n que minimice la dureza en la gr\u00e1fica, o dicho de otra forma, reducir la&nbsp; suma de distancias entre v\u00e9rtices con colores id\u00e9nticos (Lara-Vel\u00e1zquez, et al., 2015). Este modelo se utiliza en la programaci\u00f3n de eventos susceptibles de cambios, asignaci\u00f3n estable de frecuencias del espectro electromagn\u00e9tico, calendarizaci\u00f3n de actividades, asignaci\u00f3n de recursos en organizaciones, en reconocimiento de patrones en general y en particular en un algoritmo clasificador no supervisado (Flores, 2017). Se ha demostrado que es un problema de tipo NP-Duro, aunque para grafos de orden menor o igual a 20, se pueden utilizar algoritmos exactos que resuelven el problema; caso contrario es necesario el uso de t\u00e9cnicas heur\u00edsticas que dan buenas soluciones.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hay cuatro algoritmos metaheur\u00edsticos que se han utilizado para resolver este problema:<br>1. Recocido simulado.<br>2. B\u00fasqueda dispersa.<br>3. GRASP cl\u00e1sico.<br>4. H\u00edbrido k-medias\/GRASP.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Estos algoritmos se han utilizado parcialmente en diferentes aplicaciones, pero no se han realizado un estudio de la calidad de soluciones y tiempos de ejecuci\u00f3n que abarque todos los tipos de instancias, por ejemplo, b\u00fasqueda dispersa y GRASP solo se ha usado en instancias pseudoaleatorias pero no en problemas reales, y por otra parte los problemas de aplicaci\u00f3n solo se ha utilizado modelo binario (un modelo de soluci\u00f3n exacto) y recocido simulado.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Objetivo general<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Hacer un estudio de calidad de soluciones y tiempos de ejecuci\u00f3n de 4 algoritmos en instancias te\u00f3ricas y aplicadas del problema de coloraci\u00f3n de gr\u00e1ficas suaves.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Objetivos espec\u00edficos<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Recopilar instancias de prueba realizadas en trabajos anteriores (ver referencias).<\/li><li>Estudiar los algoritmos de soluci\u00f3n que se utilizar\u00e1n en el estudio comparativo.<\/li><li>Modificar y en su caso, reprogramar los algoritmos de soluci\u00f3n para resolver las instancias de prueba, tomando como funciones de desempe\u00f1o: dureza, resiliencia y tiempo de ejecuci\u00f3n.<\/li><li>An\u00e1lisis de resultados usando dise\u00f1o de experimentos.<\/li><li>Escritura de un art\u00edculo para congreso nacional.<\/li><li>Reportar los resultados obtenidos en la Id\u00f3nea Comunicaci\u00f3n de Resultados (ICR).<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr. Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr. Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp; La coloraci\u00f3n de gr\u00e1ficas suaves es una generalizaci\u00f3n del problema de coloraci\u00f3n en el que se busca encontrar una coloraci\u00f3n que minimice la dureza en la gr\u00e1fica, o dicho de otra forma, reducir la&nbsp; suma de distancias entre v\u00e9rtices con colores id\u00e9nticos (Lara-Vel\u00e1zquez,<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[78],"tags":[],"class_list":["post-2670","post","type-post","status-publish","format-standard","hentry","category-78"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/pcyti.izt.uam.mx\/?p=2670\" \/>\n<meta property=\"og:locale\" content=\"es_MX\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\" \/>\n<meta property=\"og:description\" content=\"&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr. Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr. Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp; La coloraci\u00f3n de gr\u00e1ficas suaves es una generalizaci\u00f3n del problema de coloraci\u00f3n en el que se busca encontrar una coloraci\u00f3n que minimice la dureza en la gr\u00e1fica, o dicho de otra forma, reducir la&nbsp; suma de distancias entre v\u00e9rtices con colores id\u00e9nticos (Lara-Vel\u00e1zquez,\" \/>\n<meta property=\"og:url\" content=\"https:\/\/pcyti.izt.uam.mx\/?p=2670\" \/>\n<meta property=\"og:site_name\" content=\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/pcyti\/\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-13T19:40:39+00:00\" \/>\n<meta name=\"author\" content=\"pcyti\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Escrito por\" \/>\n\t<meta name=\"twitter:data1\" content=\"pcyti\" \/>\n\t<meta name=\"twitter:label2\" content=\"Tiempo de lectura\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutos\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670\"},\"author\":{\"name\":\"pcyti\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#\\\/schema\\\/person\\\/9d093e256d84249d175f986d409d857d\"},\"headline\":\"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves.\",\"datePublished\":\"2022-08-13T19:40:39+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670\"},\"wordCount\":404,\"publisher\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#organization\"},\"articleSection\":[\"2018\"],\"inLanguage\":\"es\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670\",\"url\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670\",\"name\":\"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#website\"},\"datePublished\":\"2022-08-13T19:40:39+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670#breadcrumb\"},\"inLanguage\":\"es\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?p=2670#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Inicio\",\"item\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves.\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#website\",\"url\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/\",\"name\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"es\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#organization\",\"name\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"url\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"es\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/wp-content\\\/uploads\\\/2021\\\/12\\\/logo_pcyti_small.png\",\"contentUrl\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/wp-content\\\/uploads\\\/2021\\\/12\\\/logo_pcyti_small.png\",\"width\":71,\"height\":100,\"caption\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\"},\"image\":{\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#\\\/schema\\\/logo\\\/image\\\/\"},\"sameAs\":[\"https:\\\/\\\/www.facebook.com\\\/pcyti\\\/\"]},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/#\\\/schema\\\/person\\\/9d093e256d84249d175f986d409d857d\",\"name\":\"pcyti\",\"url\":\"https:\\\/\\\/pcyti.izt.uam.mx\\\/?author=2\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/pcyti.izt.uam.mx\/?p=2670","og_locale":"es_MX","og_type":"article","og_title":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","og_description":"&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr. Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr. Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp; La coloraci\u00f3n de gr\u00e1ficas suaves es una generalizaci\u00f3n del problema de coloraci\u00f3n en el que se busca encontrar una coloraci\u00f3n que minimice la dureza en la gr\u00e1fica, o dicho de otra forma, reducir la&nbsp; suma de distancias entre v\u00e9rtices con colores id\u00e9nticos (Lara-Vel\u00e1zquez,","og_url":"https:\/\/pcyti.izt.uam.mx\/?p=2670","og_site_name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","article_publisher":"https:\/\/www.facebook.com\/pcyti\/","article_published_time":"2022-08-13T19:40:39+00:00","author":"pcyti","twitter_card":"summary_large_image","twitter_misc":{"Escrito por":"pcyti","Tiempo de lectura":"2 minutos"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670#article","isPartOf":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670"},"author":{"name":"pcyti","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d"},"headline":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves.","datePublished":"2022-08-13T19:40:39+00:00","mainEntityOfPage":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670"},"wordCount":404,"publisher":{"@id":"https:\/\/pcyti.izt.uam.mx\/#organization"},"articleSection":["2018"],"inLanguage":"es"},{"@type":"WebPage","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670","url":"https:\/\/pcyti.izt.uam.mx\/?p=2670","name":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves. - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","isPartOf":{"@id":"https:\/\/pcyti.izt.uam.mx\/#website"},"datePublished":"2022-08-13T19:40:39+00:00","breadcrumb":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670#breadcrumb"},"inLanguage":"es","potentialAction":[{"@type":"ReadAction","target":["https:\/\/pcyti.izt.uam.mx\/?p=2670"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2670#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Inicio","item":"https:\/\/pcyti.izt.uam.mx\/"},{"@type":"ListItem","position":2,"name":"Estudio comparativo de algoritmos de soluci\u00f3n para el problema de coloraci\u00f3n de graficas suaves."}]},{"@type":"WebSite","@id":"https:\/\/pcyti.izt.uam.mx\/#website","url":"https:\/\/pcyti.izt.uam.mx\/","name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","description":"","publisher":{"@id":"https:\/\/pcyti.izt.uam.mx\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/pcyti.izt.uam.mx\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"es"},{"@type":"Organization","@id":"https:\/\/pcyti.izt.uam.mx\/#organization","name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","url":"https:\/\/pcyti.izt.uam.mx\/","logo":{"@type":"ImageObject","inLanguage":"es","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/","url":"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png","contentUrl":"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png","width":71,"height":100,"caption":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n"},"image":{"@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/pcyti\/"]},{"@type":"Person","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d","name":"pcyti","url":"https:\/\/pcyti.izt.uam.mx\/?author=2"}]}},"modified_by":"pcyti","_links":{"self":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts\/2670","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2670"}],"version-history":[{"count":0,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts\/2670\/revisions"}],"wp:attachment":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2670"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2670"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2670"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}