Approximating shallow-light trees

Guy Kortsarz, David Peleg

פרסום מחקרי: תוצר מחקר מכנסהרצאהביקורת עמיתים

תקציר

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 ינו׳ 19977 ינו׳ 1997

כנס

כנסProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
עירNew Orleans, LA, USA
תקופה5/01/977/01/97

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating shallow-light trees'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי