Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.12008/3461
How to cite
Title: | Solving the Generalized Steiner Problem in edge-survivable networks |
Authors: | Sartor, Pablo Robledo, Franco |
Type: | Reporte técnico |
Keywords: | Network design, Edge-connectivity, Survivability, Steiner problems, Metaheuristics, GRASP |
Issue Date: | 2011 |
Abstract: | The Generalized Steiner Problem with Edge-Connectivity constraints (GSP-EC) consists of computing the minimal cost subnetwork of a given feasible network where some pairs of nodes must satisfy edge-connectivity requirements. It can be applied in the design of communications networks where connection lines can fail and is known to be an NP-Complete problem. In this paper we introduce an algorithm based on GRASP (Greedy Randomized Adaptive Search Procedure), a combinatorial optimization metaheuristic that has proven to be very effective for such problems. Promising results are obtained when testing the algorithm over a set of heterogeneous network topologies and connectivity requirements; in all cases with known optimal cost, optimal or near-optimal solutions are found. |
Publisher: | UR. FI – INCO. |
Series or collection: | Reportes Técnicos 11-09 |
ISSN: | 0797-6410 |
Citation: | SARTOR, P., ROBLEDO, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011. |
License: | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
Appears in Collections: | Reportes Técnicos - Instituto de Computación |
Files in This Item:
File | Description | Size | Format | ||
---|---|---|---|---|---|
TR1109.pdf | 1,79 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License