TY - JOUR
T1 - f-sensitivity distance oracles and routing schemes
AU - Chechik, Shiri
AU - Langberg, Michael
AU - Peleg, David
AU - Roditty, Liam
N1 - Publisher Copyright:
© Springer Science+Business Media, LLC 2011.
PY - 2012/8/1
Y1 - 2012/8/1
N2 - 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.
AB - 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.
KW - Distance oracle
KW - Fault-tolerance
KW - Forbidden edges
KW - Routing scheme
KW - Sensitivity
KW - Stretch
UR - http://www.scopus.com/inward/record.url?scp=84884339760&partnerID=8YFLogxK
U2 - 10.1007/s00453-011-9543-0
DO - 10.1007/s00453-011-9543-0
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:84884339760
SN - 0178-4617
VL - 63
SP - 861
EP - 882
JO - Algorithmica
JF - Algorithmica
IS - 4
ER -