Monday, 15:45 - 16:10 h, Room: H 3008


Christian Wulff-Nilsen
Approximate distance oracles with improved preprocessing and query time


Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 2, we show that a (2k-1)-approximate distance oracle for G of size O(kn1 + 1/k) and with O(log k) query time can be constructed in O(min{kmn1/k,√k m + kn1 + c/√k }) time for some constant c. This simultaneously improves the O(kmn1/k) preprocessing and the O(k) query time of Thorup and Zwick. For any 0< ε ≤ 1, we also give an oracle of size O(kn1 + 1/k) that answers ((2 + ε)k)-approximate distance queries in O(1/ε) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erd?s. We can match the O(n1 + 1/k) size bound of Mendel and Naor for any constant ε > 0 and k = O(log n/loglog n).


Talk 2 of the invited session Mon.3.H 3008
"Distances in graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  The deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.