Título:
Solving the Generalized Steiner Problem in edge-survivable networks
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Sartor, Pablo
Robledo, Franco
Robledo, Franco
Tutor:
Tipo de documento:
Reporte técnico
Editor:
Palabras clave:
Network design
Edge-connectivity
Survivability
Steiner problems
Metaheuristics
GRASP
Edge-connectivity
Survivability
Steiner problems
Metaheuristics
GRASP
Descriptores:
Año de publicación:
2011
Contenido:
Resumen:
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.
Descripción:
Editorial:
UR. FI – INCO.
EN:
Reportes Técnicos 11-09
Financiadores:
Citación:
SARTOR, P., ROBLEDO, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/3461
ISBN:
e-ISBN:
ISSN:
0797-6410
ISMN:
Otros identificadores:
Título Obtenido:
Facultad o Servicio que otorga el Título:
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| TR1109.pdf | — | 1.75 MB | Adobe PDF |