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.