Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://bibdigital.epn.edu.ec/handle/15000/21751
Titel: | Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas. |
Autor(en): | Cordero Cárdenas, Mishelle Briggitte |
Stichwörter: | BRANCH & BOUND GENERACIÓN DE COLUMNAS |
Erscheinungsdatum: | 27-Jul-2021 |
Herausgeber: | Quito, 2021 |
Zitierform: | Cordero Cárdenas, M.B. (2021). Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas. 90 hojas. Quito : EPN. |
Zusammenfassung: | 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. |
Beschreibung: | 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 |
Art: | masterThesis |
Enthalten in den Sammlungen: | Tesis Maestría en Optimización Matemática (FC) |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
CD 11233.pdf | 1,04 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.