Approximating k-Connected m-Dominating Sets

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

תקציר

A subset S of nodes in a graph G is a k-connected m-dominating set ((k, m)-cds) if the subgraph G[S] induced by S is k-connected and every v∈ V\ S has at least m neighbors in S. In the k-Connectedm-Dominating Set ((k, m)-CDS) problem, the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. For m≥ k we obtain the following approximation ratios. For unit disk graphs we improve the ratio O(kln k) of Nutov (Inf Process Lett 140:30–33, 2018) to min{m2(m-k+1)2,k2/3}·O(ln2k)—this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(ln 2k) / ϵ2 when m≥ (1 + ϵ) k; furthermore, we obtain ratio min{mm-k+1,k}·O(ln2k) for uniform weights. For general graphs our ratio O(kln n) improves the previous best ratio O(k2ln n) of Nutov (2018) and matches the best known ratio for unit weights of Zhang et al. (INFORMS J Comput 30(2):217–224, 2018). These results are obtained by showing the same ratios for the Subsetk-Connectivity problem when the set of terminals is an m-dominating set.

שפה מקוריתאנגלית
מספר המאמר6
עמודים (מ-עד)1511-1525
מספר עמודים15
כתב עתAlgorithmica
כרך84
מספר גיליון6
תאריך מקוון מוקדם16 פבר׳ 2022
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יוני 2022

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating k-Connected m-Dominating Sets'. יחד הם יוצרים טביעת אצבע ייחודית.

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