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, ארצות הברית משך הזמן: 18 אוג׳ 2001 → 20 אוג׳ 2001

סדרות פרסומים

שם	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך	2129
ISSN (מודפס)	0302-9743
ISSN (אלקטרוני)	1611-3349

כנס

כנס	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
תקופה	18/08/01 → 20/08/01

הערה ביבליוגרפית

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 et al. / 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, ארצות הברית, 18/08/01.

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 et al.
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)

תקציר

סדרות פרסומים

כנס

הערה ביבליוגרפית

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי