Approximating k-node connected subgraphs via critical graphs

Guy Kortsarz, Zeev Nutov

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


We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were O(min{k, n/√n-k}) for both directed and undirected graphs, and O(ln k) for undirected graphs with n ≥ 6k 2, where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O(n/n-k ln 2 k), which is O(ln 2 k) except for very large values of k, namely, k = n - o(n). This algorithm is based on a new result on l-connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio O(√n ln k) for all values of n, k. Combining these two gives an algorithm with approximation ratio O(ln k·min{√k, n/n-k ln k}), which asymptotically improves the best known approximation guarantee for directed graphs for all values of n, k, and for undirected graphs for k > √n/6. Moreover, this is the first algorithm that has an approximation guarantee better than Θ(k) for all values of n, k. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.

שפה מקוריתאנגלית
עמודים (מ-עד)247-257
מספר עמודים11
כתב עתSIAM Journal on Computing
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2005

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating k-node connected subgraphs via critical graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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