Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3218Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Zamarron Escobar, Daniel Enrique. | - |
| dc.creator | Zamarron Escobar, Daniel Enrique.%386211 | - |
| dc.date.accessioned | 2022-03-24T19:52:35Z | - |
| dc.date.available | 2022-03-24T19:52:35Z | - |
| dc.date.issued | 2013-06-01 | - |
| dc.identifier.uri | https://rinacional.tecnm.mx/jspui/handle/TecNM/3218 | - |
| dc.description | 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. | es_MX |
| dc.language.iso | spa | es_MX |
| dc.publisher | Tecnológico Nacional de México | es_MX |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0 | es_MX |
| dc.subject | info:eu-repo/classification/cti/7 | es_MX |
| dc.title | Estrategias de búsqueda local para el problema de SUMCUT | es_MX |
| dc.type | info:eu-repo/semantics/masterThesis | es_MX |
| dc.contributor.director | Fraire Huacuja, Hector Joaquin.%123070 | - |
| dc.rights.access | info:eu-repo/semantics/openAccess | es_MX |
| dc.publisher.tecnm | Instituto Tecnológico de Ciudad Madero | es_MX |
| Appears in Collections: | Maestría en Ciencias de la Computación | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| G11070004_donacion_tesis_bib.pdf | 820.92 kB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
