A polylogarithmic approximation algorithm for 2-edge-connected dominating set

Amir Belgi, Zeev Nutov

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

תקציר

In the CONNECTED DOMINATING SET (CDS) problem we are given a graph G and seek a min-size dominating set S such that the subgraph G[S] of G induced by S is connected. In the 2-EDGE-CONNECTED DOMINATING SET problem G[S] should be 2-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio O(log2⁡n⋅log⁡log⁡n⋅(log⁡log⁡log⁡n)3). We also show that the SUBSET STEINER CDS problem is approximation equivalent to the GROUP STEINER TREE problem.

שפה מקוריתאנגלית
מספר המאמר106175
כתב עתInformation Processing Letters
כרך173
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2022

הערה ביבליוגרפית

Publisher Copyright:
© 2021 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A polylogarithmic approximation algorithm for 2-edge-connected dominating set'. יחד הם יוצרים טביעת אצבע ייחודית.

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