Fault-tolerant spanners for general graphs

S. Chechik, M. Langberg, D. Peleg, L. Roditty

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

תקציר

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G = (V,E) and an integer k ≥ 1, the subgraph H = (V,E'), E'⊆ E, is a spanner of stretch k (or, a kspanner) of G if δH(u, v) k δG(u, v) for every u, v 2 V , where δG0 (u, v) denotes the distance between u and v in G' Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n1+1/k), and this sizestretch tradeoff is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [Levcopoulos et al., STOC'98]. A subgraph H is an f-vertex fault tolerant kspanner of the graph G if for any set F V of size at most f and any pair of vertices u, v 2 V \ F, the distances in H satisfy δH\F (u, v) ≤ k δG\F (u, v). Levcopoulos et al. presented an efficient algorithm that given a set S of n points in Rd, constructs an f-vertex fault tolerant geometric (1+ε)-spanner for S, that is, a sparse graph H such that for every set F S of size f and any pair of points u, v 2 S \F, H\F (u, v)(1+ε)|uv|, where |uv| is the Euclidean distance between u and v. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [Czumaj & Zhao, SoCG'03]. This paper also raised as an open problem the question whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant (2k-1)-spanner of size O(f2kf+1n1+1/k log1-1/k n). Interestingly, the stretch of the spanner remains unchanged while the size of the spanner. only increases by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant 2k -1 spanner with edge set of size O(fn1+1/k) (only f times larger than standard spanners). For both edge and vertex faults, our results are shown to hold when the given graph G is weighted

שפה מקוריתאנגלית
כותר פרסום המארחSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
עמודים435-444
מספר עמודים10
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2009
אירוע41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, ארצות הברית
משך הזמן: 31 מאי 20092 יוני 2009

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

שםProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (מודפס)0737-8017

כנס

כנס41st Annual ACM Symposium on Theory of Computing, STOC '09
מדינה/אזורארצות הברית
עירBethesda, MD
תקופה31/05/092/06/09

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Fault-tolerant spanners for general graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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