Fast Dynamic Transitive Closure with Lookahead |
| |
Authors: | Piotr Sankowski Marcin Mucha |
| |
Affiliation: | 1. Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097, Warsaw, Poland
|
| |
Abstract: | In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error
algorithm with updates and queries in O(n
ω(1,1,ε)−ε
) time given a lookahead of n
ε
operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n
ε
matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n
2−ε
) time, whereas for ε=1 the time is O(n
ω−1). This is essentially optimal as it implies an O(n
ω
) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this
problem, we show an algorithm that requires
O(n\fracw2)O(n^{\frac{\omega}{2}})
time to process
n\frac12n^{\frac{1}{2}}
operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms
for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error.
All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|