A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)

Guy Even; Jon Feldman; Guy Kortsarz; Zeev Nutov

A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)

Guy Even
, Jon Feldman
, Guy Kortsarz
, Zeev Nutov

מדעי המחשב

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

ملخص

We consider the following problem: given a connected graph G = (V, εE) and an additional edge set E, find a minimum size subset of edges F ⊆E suchth at (V,ε ∪F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.

اللغة الأصلية	الإنجليزيّة
عنوان منشور المضيف	Approximation, Randomization, and Combinatorial Optimization
العنوان الفرعي لمنشور المضيف	Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings
المحررون	Luca Trevisan, Klaus Jansen, Michel Goemans, Jose D. P. Rolim
ناشر	Springer Verlag
الصفحات	90-101
عدد الصفحات	12
رقم المعيار الدولي للكتب (الإلكتروني)	3540424709
حالة النشر	نُشِر - 2015
الحدث	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 - Berkeley, الولايات المتّحدة المدة: ١٨ أغسطس ٢٠٠١ → ٢٠ أغسطس ٢٠٠١

سلسلة المنشورات

الاسم	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت	2129
رقم المعيار الدولي للدوريات (المطبوع)	0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)	1611-3349

!!Conference

!!Conference	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001
الدولة/الإقليم	الولايات المتّحدة
المدينة	Berkeley
المدة	١٨/٠٨/٠١ → ٢٠/٠٨/٠١

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001

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

Link to publication in Scopus

قم بذكر هذا

Even, G., Feldman, J., Kortsarz, G., & Nutov, Z. (2015). A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract). في L. Trevisan, K. Jansen, M. Goemans, & J. D. P. Rolim (المحررون), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings (الصفحات 90-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 2129). Springer Verlag.

Even, Guy ; Feldman, Jon ; Kortsarz, Guy وآخرون. / A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract). Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. محرر / Luca Trevisan ; Klaus Jansen ; Michel Goemans ; Jose D. P. Rolim. Springer Verlag, 2015. الصفحات 90-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dd1864e1c9b945eb87feacf910f094c6,

title = "A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)",

abstract = "We consider the following problem: given a connected graph G = (V, εE) and an additional edge set E, find a minimum size subset of edges F ⊆E suchth at (V,ε ∪F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.",

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

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001 Copyright: Copyright 2015 Elsevier B.V., All rights reserved.; 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 ; Conference date: 18-08-2001 Through 20-08-2001",

year = "2015",

language = "אנגלית",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "90--101",

editor = "Luca Trevisan and Klaus Jansen and Michel Goemans and Rolim, \{Jose D. P.\}",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

address = "גרמניה",

}

Even, G, Feldman, J, Kortsarz, G & Nutov, Z 2015, A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract). في L Trevisan, K Jansen, M Goemans & JDP Rolim (المحررون), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), المجلد 2129, Springer Verlag, الصفحات 90-101, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Berkeley, الولايات المتّحدة, ١٨/٠٨/٠١.

A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract). / Even, Guy; Feldman, Jon; Kortsarz, Guy وآخرون.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. محرر / Luca Trevisan; Klaus Jansen; Michel Goemans; Jose D. P. Rolim. Springer Verlag, 2015. صفحة 90-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 2129).

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

TY - GEN

T1 - A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)

AU - Even, Guy

AU - Feldman, Jon

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2015

Y1 - 2015

N2 - We consider the following problem: given a connected graph G = (V, εE) and an additional edge set E, find a minimum size subset of edges F ⊆E suchth at (V,ε ∪F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.

AB - We consider the following problem: given a connected graph G = (V, εE) and an additional edge set E, find a minimum size subset of edges F ⊆E suchth at (V,ε ∪F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.

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

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:84923116061

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 90

EP - 101

BT - Approximation, Randomization, and Combinatorial Optimization

A2 - Trevisan, Luca

A2 - Jansen, Klaus

A2 - Goemans, Michel

A2 - Rolim, Jose D. P.

PB - Springer Verlag

T2 - 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001

Y2 - 18 August 2001 through 20 August 2001

ER -

Even G, Feldman J, Kortsarz G, Nutov Z. A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract). في Trevisan L, Jansen K, Goemans M, Rolim JDP, المحررون, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. Springer Verlag. 2015. صفحة 90-101. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)

ملخص

سلسلة المنشورات

!!Conference

ملاحظة ببليوغرافية

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

بصمة

قم بذكر هذا