Degree-constrained node-connectivity

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

תקציר

We give a general framework to handle node-connectivity degree constrained problems. In particular, for the κ-Outconnected Subgraph problem, for both directed and undirected graphs, our algorithm computes in polynomial time a solution J of cost O(log κ) times the optimal, such that deg J (v) = O(2 κ ) • b(v) for all ν ∈ V. Similar result are obtained for the Element-Connectivity and the κ-Connected Subgraph problems. The latter is a significant improvement on the particular case of only degree-approximation and undirected graphs considered in [5]. In addition, for the edge-connectivity directed Degree-Constrained κ-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof.

שפה מקוריתאנגלית
כותר פרסום המארחLATIN 2012
כותר משנה של פרסום המארחTheoretical Informatics - 10th Latin American Symposium, Proceedings
עמודים582-593
מספר עמודים12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2012
אירוע10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, פרו
משך הזמן: 16 אפר׳ 201220 אפר׳ 2012

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

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

כנס

כנס10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
מדינה/אזורפרו
עירArequipa
תקופה16/04/1220/04/12

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Degree-constrained node-connectivity'. יחד הם יוצרים טביעת אצבע ייחודית.

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