Approximating minimum-power k-connectivity

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


The Minimum-Power k-Connected Subgraph (MPkCS) problem seeks a power (range) assignment to the nodes of a given wireless network such that the resulting communication (sub)network is k-connected and the total power is minimum. We give a new very simple approximation algorithm for this problem that significantly improves the previously best known approximation ratios. Specifically, the approximation ratios of our algorithm are: - 3 (improving (3 + 2/3)) for k = 2; - 4 (improving (5 + 2/3)) for k = 3; - k + 3 for k ∈ {4, 5} and k + 5 for k ∈ {6, 7} (improving k + 2[(k + 1)/2]); - 3(k - 1) (improving 3k) for any constant k. Our results are based on a (k + 1)-approximation algorithm (improving the ratio k + 4) for the problem of finding a Min-Power k-Inconnected Subgraph, which is of independent interest.

שפה מקוריתאנגלית
עמודים (מ-עד)129-137
מספר עמודים9
כתב עתAd-Hoc and Sensor Wireless Networks
מספר גיליון1-2
סטטוס פרסוםפורסם - 2010

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating minimum-power k-connectivity'. יחד הם יוצרים טביעת אצבע ייחודית.

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