Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas.

Cordero Cárdenas, Mishelle Briggitte

Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/21751

Registro completo de metadatos

Campo DC	Valor	Lengua/Idioma
dc.contributor.author	Cordero Cárdenas, Mishelle Briggitte	-
dc.date.accessioned	2021-07-28T17:33:25Z	-
dc.date.available	2021-07-28T17:33:25Z	-
dc.date.issued	2021-07-27	-
dc.identifier.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.	es_ES
dc.identifier.other	T-MVE/0913/CD 11233	-
dc.identifier.uri	http://bibdigital.epn.edu.ec/handle/15000/21751	-
dc.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.	es_ES
dc.description.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.	es_ES
dc.description.sponsorship	Recalde Calahorrano, Diego Fernando, director	es_ES
dc.language.iso	spa	es_ES
dc.publisher	Quito, 2021	es_ES
dc.rights	openAccess	es_ES
dc.subject	BRANCH & BOUND	es_ES
dc.subject	GENERACIÓN DE COLUMNAS	es_ES
dc.title	Particionamiento de un Grafo General en k Componentes Conexas usando Generación de Columnas.	es_ES
dc.type	masterThesis	es_ES
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

Muestra el registro sencillo del ítem

BIBDIGITAL