Please use this identifier to cite or link to this item:
http://bibdigital.epn.edu.ec/handle/15000/24866
Title: | Particionamiento Balanceado de Hipergrafos en un Número Fijo de Componentes. |
Authors: | Landázuri Mejía, Guillermo Andrés |
Director: | Recalde Calahorrano, Diego Fernando |
Keywords: | PARTICIONAMIENTO DE HIPERGRAFOS EQUIPARTICIONAMIENTO DESIGUALDADES VÁLIDAS PROGRAMACIÓN ENTERA OPTIMIZACIÓN EN GRAFOS |
Issue Date: | 28-Sep-2023 |
Publisher: | Quito : EPN, 2023. |
Citation: | Landázuri Mejía, G.A.(2023).Particionamiento Balanceado de Hipergrafos en un Número Fijo de Componentes.88 páginas. Quito : EPN. |
Abstract: | In this paper, the partitioning hypergraph problem in a fixed number of components is studied. Hypergraphs are the generalization of graphs where, unlike edges, each hyperedge can connect two or more vertices. Given a hypergraph H = (V,E), where V is the vertices set and E the hyperedges set, we seek to partition its vertex set into k disjoint components such that each vertex is covered by hyperedges completely contained in some component, while minimizing the total cost of these hyperedges. Several Integer Programming formulations are proposed for the k-way equipartitioning, minimum size partitioning, balanced partitioning, and k-way equipartitioning in linear hyper-trees. Moreover, some types of valid inequalities are demonstrated and implemented for the different formulations. Finally, the computational experiments performed on the different formulations for different instances are discussed. |
Description: | En el presente trabajo se estudia el problema de particionamiento de hipergrafos en un número fijo de componentes. Los hipergrafos son la generalización de los grafos donde, en lugar de aristas, cada hiperarista puede conectar dos o más vértices. Dado un hipergrafo H = (V,E), donde V es el conjunto de vértices y E es el conjunto de hiperaristas, se busca dividir su conjunto de vértices en k componentes disjuntas tal que cada vértice esté cubierto únicamente por hiperaristas contenidas completamente en alguna componente, a la vez que se minimiza el costo total de estas hiperaristas. Se proponen varias formulaciones de Programación Entera para los problemas de k-equiparticionamiento, particionamiento de tamaño mínimo, particionamiento balanceado y k-equiparticionamiento en hiperárboles lineales. Además, se presentan algunos tipos de desigualdades válidas a ser implementadas en las diferentes formulaciones. Finalmente, se discuten los resultados computacionales realizadas en las diferentes formulaciones para distintas instancias. |
URI: | http://bibdigital.epn.edu.ec/handle/15000/24866 |
Type: | masterThesis |
Appears in Collections: | Tesis Maestría en Optimización Matemática (FC) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CD 13537.pdf | 22,64 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.