תקציר
We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, E) and an edge set E on V disjoint to E, find a minimum-size subset of edges F ⊆ E such that (V, E ∪ F) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.
שפה מקורית | אנגלית |
---|---|
מספר המאמר | 21 |
כתב עת | ACM Transactions on Algorithms |
כרך | 5 |
מספר גיליון | 2 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 1 מרץ 2009 |