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 |
Type: | masterThesis |
Appears in Collections: | Tesis Maestría en Optimización Matemática (FC) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CD 11233.pdf | 1,04 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.