Please use this identifier to cite or link to this item: http://bibdigital.epn.edu.ec/handle/15000/21751
Title: Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas.
Authors: Cordero Cárdenas, Mishelle Briggitte
Keywords: BRANCH & BOUND
GENERACIÓN DE COLUMNAS
Issue Date: 27-Jul-2021
Publisher: Quito, 2021
Citation: Cordero Cárdenas, M.B. (2021). Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas. 90 hojas. Quito : EPN.
Abstract: 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.
Description: 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
Appears in Collections:Tesis Maestría en Optimización Matemática (FC)

Files in This Item:
File Description SizeFormat 
CD 11233.pdf1,04 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.