Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs

Details Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs

2011-04-27

arxiv.org/abs/1104.5214v1

Computer Science

Data Structures and Algorithms

Scientific paper

10.1007/978-3-642-22006-7_12

A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of \epsilon and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.

Affiliated with

Also associated with

No associations

Rating

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-476334