Paper Info
Title
Brief announcement: a simple stretch 2 distance oracle
Abstract
We present a distance oracle that, for weighted graphs with n vertices and m edges, is of size 8n4/3m1/3log2/3n and returns stretch-2 distances in constant time. Our oracle achieves bounds identical to the constant-time stretch-2 oracle of Pǎtraşcu and Roditty, but admits significantly simpler construction and proofs.
Year
DOI
Venue
2013
10.1145/2484239.2484277
PODC
Keywords
Field
DocType
stretch-2 oracle,simple stretch,simpler construction,n vertex,m edge,brief announcement,returns stretch-2 distance,constant time,weighted graph,distance oracle
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Computer science,Oracle,Mathematical proof
Conference
Citations 
PageRank 
References 
1
0.35
9
Authors
2
Name
Order
Citations
PageRank
Rachit Agarwal138126.19
P. Brighten Godfrey22519145.37