Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5

Yefim Dinitz; Zeev Nutov

doi:10.1007/3-540-62592-5_57

Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5

Yefim Dinitz
, Zeev Nutov

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

תקציר

The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.

שפה מקורית	אנגלית
כותר פרסום המארח	Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings
עורכים	Giancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista
מוציא לאור	Springer Verlag
עמודים	13-24
מספר עמודים	12
מסת"ב (מודפס)	3540625925, 9783540625926
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1007/3-540-62592-5_57
סטטוס פרסום	פורסם - 1997
פורסם באופן חיצוני	כן
אירוע	3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, איטליה משך הזמן: 12 מרץ 1997 → 14 מרץ 1997

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

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

כנס

כנס	3rd Italian Conference on Algorithms and Complexity, CIAC 1997
מדינה/אזור	איטליה
עיר	Rome
תקופה	12/03/97 → 14/03/97

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

גישה למסמך

10.1007/3-540-62592-5_57

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

Link to publication in Scopus

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

Dinitz, Y., & Nutov, Z. (1997). Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5. ב- G. Bongiovanni, D. P. Bovet, & G. Di Battista (עורכים), Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings (עמודים 13-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 1203). Springer Verlag. https://doi.org/10.1007/3-540-62592-5_57

Dinitz, Yefim ; Nutov, Zeev. / Finding optimum k-vertex connected spanning subgraphs : Improved approximation algorithms for k=3, 4, 5. Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings. עורך / Giancarlo Bongiovanni ; Daniel Pierre Bovet ; Giuseppe Di Battista. Springer Verlag, 1997. עמודים 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{09b5c733137a4aa38f9f1228a7e75273,

title = "Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5",

abstract = "The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.",

author = "Yefim Dinitz and Zeev Nutov",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 ; Conference date: 12-03-1997 Through 14-03-1997",

year = "1997",

doi = "10.1007/3-540-62592-5\_57",

language = "אנגלית",

isbn = "3540625925",

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

publisher = "Springer Verlag",

pages = "13--24",

editor = "Giancarlo Bongiovanni and Bovet, \{Daniel Pierre\} and \{Di Battista\}, Giuseppe",

booktitle = "Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings",

address = "גרמניה",

}

Dinitz, Y & Nutov, Z 1997, Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5. ב- G Bongiovanni, DP Bovet & G Di Battista (עורכים), Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), כרך 1203, Springer Verlag, עמודים 13-24, 3rd Italian Conference on Algorithms and Complexity, CIAC 1997, Rome, איטליה, 12/03/97. https://doi.org/10.1007/3-540-62592-5_57

Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5. / Dinitz, Yefim; Nutov, Zeev.
Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings. עורך / Giancarlo Bongiovanni; Daniel Pierre Bovet; Giuseppe Di Battista. Springer Verlag, 1997. עמוד 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 1203).

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

TY - GEN

T1 - Finding optimum k-vertex connected spanning subgraphs

T2 - 3rd Italian Conference on Algorithms and Complexity, CIAC 1997

AU - Dinitz, Yefim

AU - Nutov, Zeev

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.

AB - The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.

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

U2 - 10.1007/3-540-62592-5_57

DO - 10.1007/3-540-62592-5_57

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

AN - SCOPUS:84957609587

SN - 3540625925

SN - 9783540625926

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

SP - 13

EP - 24

BT - Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings

A2 - Bongiovanni, Giancarlo

A2 - Bovet, Daniel Pierre

A2 - Di Battista, Giuseppe

PB - Springer Verlag

Y2 - 12 March 1997 through 14 March 1997

ER -

Dinitz Y, Nutov Z. Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5. ב- Bongiovanni G, Bovet DP, Di Battista G, עורכים, Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings. Springer Verlag. 1997. עמוד 13-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-62592-5_57

Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5

תקציר

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

כנס

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

גישה למסמך

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

טביעת אצבע

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