f-sensitivity distance oracles and routing schemes

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

An f-sensitivity distance oraclefor a weighted undirected graphG(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructiblef-sensitivity distance oracle that given a triplet (s,t,F), wheresandtare vertices andFis a set of forbidden edges such that |F|≤f, returns an estimate of the distance betweensandtinG(V,E∖F). For an integer parameterk≥1, the size of the data structure isO(fkn1+1/klog (nW)), whereWis the heaviest edge inG, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time isO(|F|⋅log 2n⋅log log n⋅log log d), wheredis the distance betweensandtinG(V,E∖F). Our result differs from previous ones in two major respects: (1) it is the first to considerapproximateoracles for general graphs (and thus obtain a succinct data structure); (2) our result holds for an arbitrary number of forbidden edges. In contrast, previous papers concernf-sensitiveexactdistance oracles, which consequently have size Ω(n2). Moreover, those oracles support forbidden setsFof size |F|≤2. The paper also considersf-sensitive compact routing schemes, namely, routing schemes that avoid a given set of forbidden (orfailed) edges. It presents a scheme capable of withstanding up to two edge failures. Given a messageMdestined totat a source vertexs, in the presence of a forbidden edge setFof size |F|≤2 (unknown tos), our scheme routesMfromstotin a distributed manner, over a path of length at mostO(k) times the length of the optimal path (avoidingF). The total amount of information stored in vertices ofGisO(kn1+1/klog (nW)log n). To the best of our knowledge, this is the first result obtaining anf-sensitive compact routing scheme for general graphs.

שפה מקוריתאנגלית
עמודים (מ-עד)861-882
מספר עמודים22
כתב עתAlgorithmica
כרך63
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוג׳ 2012

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

Publisher Copyright:
© Springer Science+Business Media, LLC 2011.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'f-sensitivity distance oracles and routing schemes'. יחד הם יוצרים טביעת אצבע ייחודית.

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