On the hardness of distance oracle for sparse graph

Details On the hardness of distance oracle for sparse graph On the hardness of distance oracle for sparse graph

2010-06-06

arxiv.org/abs/1006.1117v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we show that set-intersection is harder than distance oracle on sparse graphs. Given a collection of total size n which consists of m sets drawn from universe U, the set-intersection problem is to build a data structure which can answer whether two sets have any intersection. A distance oracle is a data structure which can answer distance queries on a given graph. We show that if one can build distance oracle for sparse graph G=(V,E), which requires s(|V|,|E|) space and answers a (2-\epsilon,c)-approximate distance query in time t(|V|,|E|) where (2-\epsilon) is a multiplicative error and c is a constant additive error, then, set-intersection can be solved in t(m+|U|,n) time using s(m+|U|,n) space.

Affiliated with

Also associated with

No associations

Rating

On the hardness of distance oracle for sparse 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 On the hardness of distance oracle for sparse graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the hardness of distance oracle for sparse graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-682279