ﻻ يوجد ملخص باللغة العربية
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 following: * Given a desired space allocation $Sin[nlglg n,n^2]$, we show how to construct in $tilde O(S)$ time a data structure of size $O(S)$ that answers distance queries in $tilde O(n/sqrt S)$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $kin[sqrt n,n)$. * We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+eps})$ for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space $tilde O(n)$ such that for any pair of nodes at distance D the query time is $tilde O(min {D,sqrt n})$. Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(sqrt n)$ nodes, we can preprocess G in $tilde O(n)$ time to produce a data structure of size $O(n lglg c)$ that can answer the following queries in $tilde O(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA06), Djidjev (WG96), and Fakcharoenphol and Rao (FOCS01). For $sigmain(1,4/3)$ and space $S=n^sigma$, we essentially improve the query time from $n^2/S$ to $sqrt{n^2/S}$.
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
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
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-
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 s
Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allowed to make a single left-to-right pass through the array and the key