ﻻ يوجد ملخص باللغة العربية
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph $G$ with $n$ nodes and integer weights from $[-W,W]$. Second, given a single batch of $f$ edge insertions and deletions, we update the data structure. Third, given a query pair of nodes $(u,v)$, return the distance from $u$ to $v$. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from $u$ to $v$. Our first result is a sensitive distance oracle with $tilde{O}(Wn^{omega+(3-omega)mu})$ preprocessing time, $tilde{O}(Wn^{2-mu}f^{2}+Wnf^{omega})$ update time, and $tilde{O}(Wn^{2-mu}f+Wnf^{2})$ query time where the parameter $muin[0,1]$ can be chosen. The data-structure requires $O(Wn^{2+mu} log n)$ bits of memory. This is the first algorithm that can handle $fgelog n$ updates. Previous results (e.g. [Demetrescu et al. SICOMP08; Bernstein and Karger SODA08 and FOCS09; Duan and Pettie SODA09; Grandoni and Williams FOCS12]) can handle at most 2 updates. When $3le flelog n$, the only non-trivial algorithm was by [Weimann and Yuster FOCS10]. When $W=tilde{O}(1)$, our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when $f=omega(1)$, their update and query time is $Omega(n^{2-o(1)})$, while our update and query time are truly subquadratic in $n$, i.e., ours is faster by a polynomial factor of $n$. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp05; Zhou, Labahn and Storjohann J.Comp15] developed in the symbolic computation community. [...]
We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the fo
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing t
One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large po
Many context-sensitive data flow analyses can be formulated as a variant of the all-pairs Dyck-CFL reachability problem, which, in general, is of sub-cubic time complexity and quadratic space complexity. Such high complexity significantly limits the
Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and th