Degree constrained node-connectivity problems

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

תקציר

We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(logk) times the optimal, with degrees O(2 k )·b(v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O(klogn)·b(v) in O(n k ) time on undirected graphs by Feder, Motwani, and Zhu.

שפה מקוריתאנגלית
עמודים (מ-עד)340-364
מספר עמודים25
כתב עתAlgorithmica
כרך70
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוק׳ 2014

טביעת אצבע

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

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