Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.12008/2917
How to cite
Title: | Diseño topológico de redes : casos de estudio :"The generalized Steiner problem"and "The Steiner 2-edge-connected subgraph problem" |
Authors: | Robledo, Franco |
Obtained title: | Magíster en Informática |
University or service that grants the title: | Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación – PEDECIBA |
Tutor: | Cancela, Héctor Viera, Omar |
Type: | Tesis de maestría |
Keywords: | Diseño topológico, Redes, Requerimientos de conexión, Subgrafo2-arista-conexo, Algoritmo exacto, Algoritmo paralelo distribuído, Algoritmo aproximado, Metaheurística Ant System |
Issue Date: | 2000 |
Abstract: | Dado un grafo G=(V,E), una matriz C de costos asociados a las aristas, un subconjunto T de nodos denominados terminales y una matriz R de requerimientos de conexión entre nodos terminales, el "Generalized Steiner Problem" (GSP)consiste en encontrar un subgrafo Gs de G de costo mínimo tal que para todo par de nodos terminales existen al menos Rij caminos de aristas-disjuntas en Gs. Un grafo se dice 2-arista-conexo si entre todo par de nodos existen al menos 2 caminos de aristas disjuntas que los unen. Dos casos particulares de GSP son: encontrar un subgrafo Gs de G 2-arista-conexo de costo mínimo que cubra el conjunto de nodos terminales T, este problema es conocido como "Steiner 2-edge-connected subgraph problem"(STECSP), - encontrar un subgrafo Gs de G de costo mínimo tal que para todo par de nodos terminales existen al menos 2 caminos de aristas disjuntas que los unen, este problema es conocido como "Steiner 2-edge survivable subgraph problem" (STESNP). |
Publisher: | UR. FI-INCO, |
Citation: | ROBLEDO, F. "Diseño topológico de redes : casos de estudio : "The generalized Steiner problem"and "The Steiner 2-edge-connected subgraph problem"". Tesis de maestría, Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación; PEDECIBA, 2000. |
License: | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
Appears in Collections: | Tesis de posgrado - Instituto de Computación |
Files in This Item:
File | Description | Size | Format | ||
---|---|---|---|---|---|
tesism-robledo.pdf | 1,15 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License