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)
סטטוס פרסוםפורסם - 1 מרץ 2009

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2'. יחד הם יוצרים טביעת אצבע ייחודית.

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