A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

Vincenzo Auletta, Yefim Dinitz, Zeev Nutov, Domenico Parente

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

תקציר

The problem of finding a minimum weight k-vertex connected spanning subgraph in a graph G = (V, E) is considered. For k ≥ 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there exist k internally vertex-disjoint paths to every other vertex), we derive polynomial time algorithm for finding a ([k/2] + 1)-connected subgraph with a weight at most twice the optimum to the original problem. In particular, we obtain a 2-approximation algorithm for the case k = 3 of our problem. This improves the best previously known approximation ratio 3. The complexity of the algorithm is O(|V|3|E|) = O(|V|5).

שפה מקוריתאנגלית
עמודים (מ-עד)21-30
מספר עמודים10
כתב עתJournal of Algorithms
כרך32
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 1999
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph'. יחד הם יוצרים טביעת אצבע ייחודית.

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