On the hardness of approximating spanners

G. Kortsarz

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


A k-spanner of a connected graph G = (V, E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than the distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k, approximating the spanner problem is at least as hard as approximating the set-cover problem. We also consider a weighted version of the spanner problem, and prove an essential difference between the approximability of the case k = 2 and the case k ≥ 5.

שפה מקוריתאנגלית
עמודים (מ-עד)432-450
מספר עמודים19
כתב עתAlgorithmica
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2001

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the hardness of approximating spanners'. יחד הם יוצרים טביעת אצבע ייחודית.

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