תקציר
This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set, V of ν vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d≤5. Here we give a polynomial time approximation algorithm of ratio d log ν for constant d, and an algorithm of ratio νε, for any fixed 0<ε<1, for general d.
שפה מקורית | אנגלית |
---|---|
עמודים | 103-110 |
מספר עמודים | 8 |
סטטוס פרסום | פורסם - 1997 |
אירוע | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA משך הזמן: 5 ינו׳ 1997 → 7 ינו׳ 1997 |
כנס
כנס | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
עיר | New Orleans, LA, USA |
תקופה | 5/01/97 → 7/01/97 |