<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes |
| |
Authors: | Shiri Chechik Michael Langberg David Peleg Liam Roditty |
| |
Affiliation: | 1.Dept. of Computer Science and Applied Math.,The Weizmann Institute,Rehovot,Israel;2.Computer Science Division,Open University of Israel,Raanana,Israel;3.Department of Computer Science,Bar-Ilan University,Ramat-Gan,Israel |
| |
Abstract: | An f-sensitivity distance oracle for a weighted undirected graph G(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 constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn
1+1/k
log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log 2
n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|