(1+epsilon)-Distance Oracle for Planar Labeled Graph

Details (1+epsilon)-Distance Oracle for Planar Labeled Graph (1+epsilon)-Distance Oracle for Planar Labeled Graph

2011-12-29

arxiv.org/abs/1112.6256v2

Computer Science

Data Structures and Algorithms

Scientific paper

Given a vertex-labeled graph, each vertex $v$ is attached with a label from a set of labels. The vertex-label query desires the length of the shortest path from the given vertex to the set of vertices with the given label. We show how to construct an oracle if the given graph is planar, such that $O(\frac{1}{\epsilon}n\log n)$ storing space is needed, and any vertex-label query could be answered in $O(\frac{1}{\epsilon}\log n\log \rho)$ time with stretch $1+\epsilon$. $\rho$ is the radius of the given graph, which is half of the diameter. For the case that $\rho = O(\log n)$, we construct an oracle that achieves $O(\log n)$ query time, without changing the order of storing space.

Affiliated with

Also associated with

No associations

Rating

(1+epsilon)-Distance Oracle for Planar Labeled Graph 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 (1+epsilon)-Distance Oracle for Planar Labeled Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (1+epsilon)-Distance Oracle for Planar Labeled Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-728395