Loading...
Please wait, while we are loading the content...
Similar Documents
Object Location Using Path Separators
| Content Provider | CiteSeerX |
|---|---|
| Author | Abraham, Ittai |
| Abstract | We study a novel separator property called k-path separable. Roughly speaking, a k-path separable graph can be recursively separated into smaller components by sequentially removing k shortest paths. Our main result is that every minor free weighted graph is k-path separable. We then show that k-path separable graphs can be used to solve several object location problems: (1) a small-worldization with an average poly-logarithmic number of hops; (2) an (1 + ε)approximate distance labeling scheme with O(log n) space labels; (3) a stretch-(1 + ε) compact routing scheme with tables of poly-logarithmic space; (4) an (1+ε)-approximate distance oracle with O(n log n) space and O(log n) query time. Our results generalizes to much wider classes of weighted graphs, namely to bounded-dimension isometric sparable graphs. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Average Poly-logarithmic Number Several Object Location Problem Approximate Distance Oracle K-path Separable Graph Approximate Distance K-path Separable Poly-logarithmic Space Space Label Bounded-dimension Isometric Sparable Graph Object Location Using Path Separator Much Wider Class Novel Separator Property |
| Content Type | Text |
