BIBDIGITAL
El Repositorio Digital Institucional de la Escuela Politécnica Nacional, ofrece acceso abierto al texto completo de la producción científica de los miembros de la comunidad politécnica. El objetivo del Repositorio, es constituirse como el registro permanente de consulta académica, maximizando su visibilidad, accesibilidad e impacto.
Por favor, use este identificador para citar o enlazar este ítem:
http://bibdigital.epn.edu.ec/handle/15000/21751| Título: | Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas. |
| Autor: | Cordero Cárdenas, Mishelle Briggitte |
| Palabras clave: | BRANCH & BOUND GENERACIÓN DE COLUMNAS |
| Fecha de publicación: | 27-jul-2021 |
| Editorial: | Quito, 2021 |
| Citación: | Cordero Cárdenas, M.B. (2021). Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas. 90 hojas. Quito : EPN. |
| Resumen: | In this work we study the problem of partitioning general graphs into a fixed number of connected components. The problem takes as input an undirected general graph G := (V, E) with costs on the edges. The partitioning problem consists of partitioning the set of nodes into a fixed number of subsets such that each subset induces a connected subgraph and the total cost of the edges in each subgraph must be minimized. Three Integer Programming formulations are provided and a heuristic method for column generation is proposed. Finally, computational results based on simulated instances are reported. |
| Descripción: | En este trabajo se estudia el problema de particionamiento de grafos generales en un número fijo de componentes conexas. El problema toma como entrada un grafo general no dirigido G := (V, E) con costos en las aristas. El problema de particionamiento consiste en dividir el conjunto de nodos en un número fijo de subconjuntos tal que cada subconjunto induzca un subgrafo conexo y el costo total de las aristas en cada subgrafo sea minimizado. Se presentan tres formulaciones de Programación Entera y se propone un método heurístico de generación de columnas. Finalmente, resultados computacionales basados en instancias simuladas son reportados. |
| URI: | http://bibdigital.epn.edu.ec/handle/15000/21751 |
| Tipo: | masterThesis |
| Aparece en las colecciones: | Tesis Maestría en Optimización Matemática (FC) |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| CD 11233.pdf | 1,04 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.