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

Guy Even; Jon Feldman; Guy Kortsarz; Zeev Nutov

doi:10.1145/1497290.1497297

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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1145/1497290.1497297
حالة النشر	نُشِر - 1 مارس 2009

الوصول إلى المستند

10.1145/1497290.1497297

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{115e4b4d668843a984e1a93341a2a5bb,

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

abstract = "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.",

keywords = "Approximation algorithms, Connectivity, Graphs",

author = "Guy Even and Jon Feldman and Guy Kortsarz and Zeev Nutov",

year = "2009",

month = mar,

day = "1",

doi = "10.1145/1497290.1497297",

language = "אנגלית",

volume = "5",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

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

AU - Even, Guy

AU - Feldman, Jon

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2009/3/1

Y1 - 2009/3/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Connectivity

KW - Graphs

UR - https://www.scopus.com/pages/publications/67149143139

U2 - 10.1145/1497290.1497297

DO - 10.1145/1497290.1497297

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:67149143139

SN - 1549-6325

VL - 5

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 21

ER -

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

ملخص

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا