Approximating the weight of shallow steiner 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 of v 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 O(log v) for constant d, which is asymptotically optimal unless P = NP, and an algorithm of ratio O(vε), for any fixed 0 < ε < 1, for general d.

שפה מקוריתאנגלית
עמודים (מ-עד)265-285
מספר עמודים21
כתב עתDiscrete Applied Mathematics
מספר גיליון2-3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 20 יולי 1999

טביעת אצבע

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

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