A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

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

بصمة

أدرس بدقة موضوعات البحث “A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا