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
מזהי עצם דיגיטלי (DOIs)	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

תקציר

גישה למסמך

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

טביעת אצבע

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