ملخص
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 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 1 مارس 2009 |