Ver Estadísticas

Tesis Validadas: 2,591

Tesis de Posgrado: 3,262

Visitas: 307

  1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
  2. Tesis de Posgrado
  3. Tamaulipas
  4. Instituto Tecnológico de Ciudad Madero
  5. Tesis
  6. Tesis de Maestría
  7. Maestría en Ciencias de la Computación

Por favor, use este identificador para citar o enlazar este ítem: https://rinacional.tecnm.mx/jspui/handle/TecNM/3218
Título : Estrategias de búsqueda local para el problema de SUMCUT
Autor : Zamarron Escobar, Daniel Enrique.
Fecha de publicación : 2013-06-01
Editorial : Tecnológico Nacional de México
metadata.dc.publisher.tecnm: Instituto Tecnológico de Ciudad Madero
Descripción : En este trabajo de investigaci´on se aborda el problema de dise˜nar estrategias eficientes de b´usqueda local para el problema del SUMCUT. El SUMCUT es un problema NP-duro que consiste en minimizar la suma de los cortes de un grafo conexo; dicho problema tiene aplicaciones en la gen´etica, en la arqueolog´ıa y en la reducci´on de matrices dispersas. La contribuci´on m´as importante de este tra bajo consiste en cinco nuevas estrategias de b´usqueda local, la cuales incorporan mecanismos eficientes para la predicci´on del costo de una inserci´on consecutiva los cuales reducen la complejidad de las b´usquedas locales de O(n 3 ) a O(n 2 ). Para validar la eficiencia de las estrategias propuestas se desarroll´o una soluci´on metaheur´ıstica del problema SUMCUT, basada en una b´usqueda local iterada con procesamiento celular. Se realizaron pruebas experimentales con instancias est´andar, los cuales mostraron que para las instancias m´as grandes que las b´usque das locales propuestas, reducen el tiempo de ejecuci´on del algoritmo al menos un 90 % alcanzando el mismo nivel de calidad. Resultados parciales de este trabajo se incorporaron en el art´ıculo “Estrategias de b´usqueda local para el problema de SUMCUT”, el cual fue publicado en el VI Encuentro de Investigadores de Posgrado en el ´area de Ciencias Computacionales realizado en el Instituto Tecnol´ogico de Ciudad Madero los d´ıas del 10 al 14 de diciembre del 2012.
metadata.dc.type: info:eu-repo/semantics/masterThesis
Aparece en las colecciones: Maestría en Ciencias de la Computación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
G11070004_donacion_tesis_bib.pdf820.92 kBAdobe PDFVisualizar/Abrir


Este ítem está protegido por copyright original

Visualizar la licencia
Mostrar el registro Dublin Core completo del ítem


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons