2-node-connectivity network design

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


We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. • In the 1-CONNECTIVITY AUGMENTATION problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general CROSSING FAMILY COVER problem. • In the 2-CONNECTED DOMINATING SET problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio O(σ(n)⋅log3⁡n), where σ(n)=O(log⁡n⋅log⁡log⁡n⋅(log⁡log⁡log⁡n)3). The unifying technique of both results is a reduction to the SUBSET STEINER CONNECTED DOMINATING SET problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

שפה מקוריתאנגלית
מספר המאמר114367
כתב עתTheoretical Computer Science
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 מרץ 2024

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

Publisher Copyright:
© 2023 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום '2-node-connectivity network design'. יחד הם יוצרים טביעת אצבע ייחודית.

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