Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | en |
| Published: |
Universidad de Tarapacá
2000
|
| Subjects: | |
| Online Access: | https://www.redalyc.org/articulo.oa?id=11400803 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- El Problema del 2-Arbol de Cubrimiento de Peso Mínimo y Redes Inmunes a Fallas Aisladas Hector Beck Fernández Alfredo Candia Vejar Ingeniería The problem of finding a Minimum Cost Spanning 2-Tree is studied from a complete edge-weighted undirected graph,and its relationship with the Networks Immune to Isolated Failures. The only algorithm known to find the exactsolution of the general problem has computational complexity of exponential time. Furthermore, it is demonstratedthat the original recurrence equations that allow to find the optimal solutionto the problem, have mistakes and weprovide the correct equations. We also suggest three heuristics, which are practical., We compared them with otherheuristics and with the exact solution when possible. We concluded that designing networks immune to isolated failures corresponds to the problem of finding a minimum cost spanning 2-tree and that the heuristics that areoutlined deliver feasible, good quality solutions and better approximation than previous works 2000 artículo científico 0717-1072 https://www.redalyc.org/articulo.oa?id=11400803 en http://www.redalyc.org/revista.oa?id=114 Revista Facultad de Ingeniería application/pdf Universidad de Tarapacá Revista Facultad de Ingeniería (Chile) Num.8