Solving the Generalized Steiner Problem in edge-survivable networks

dc.creatorSartor, Pablo
dc.creatorRobledo Amoza, Franco Rafael
dc.date.accessioned2014-12-02T16:06:24Z
dc.date.accessioned2022-10-28T19:22:08Z
dc.date.available2014-12-02T16:06:24Z
dc.date.available2022-10-28T19:22:08Z
dc.date.created2014-12-02T16:06:24Z
dc.date.issued2011
dc.identifierSARTOR, P., ROBLEDO AMOZA, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011.
dc.identifier0797-6410
dc.identifierhttp://hdl.handle.net/20.500.12008/3461
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/4959839
dc.description.abstractThe 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.
dc.publisherUR. FI – INCO.
dc.relationReportes Técnicos 11-09
dc.rightsLicencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
dc.rightsLas obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad De La República. (Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)
dc.subjectNetwork Design
dc.subjectEdge-connectivity
dc.subjectSurvivability
dc.subjectSteiner Problems
dc.subjectMetaheuristics
dc.subjectGRASP
dc.titleSolving the Generalized Steiner Problem in edge-survivable networks
dc.typeReporte técnico


Este ítem pertenece a la siguiente institución