Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Improved Bounds for Shortest Paths in Dense Distance Graphs   We study the problem of computing shortest paths in so-called dense distance
graphs. Every planar graph $G$ on $n$ vertices can be partitioned into a set of
$O(n/r)$ edge-disjoint regions (called an $r$-division) with $O(r)$ vertices
each, such that each region has $O(\sqrt{r})$ vertices (called boundary
vertices) in common with other regions. A dense distance graph of a region is a
complete graph containing all-pairs distances between its boundary nodes. A
dense distance graph of an $r$-division is the union of the $O(n/r)$ dense
distance graphs of the individual pieces. Since the introduction of dense
distance graphs by Fakcharoenphol and Rao, computing single-source shortest
paths in dense distance graphs has found numerous applications in fundamental
planar graph algorithms.
  Fakcharoenphol and Rao proposed an algorithm (later called FR-Dijkstra) for
computing single-source shortest paths in a dense distance graph in
$O\left(\frac{n}{\sqrt{r}}\log{n}\log{r}\right)$ time. We show an
$O\left(\frac{n}{\sqrt{r}}\left(\frac{\log^2{r}}{\log^2\log{r}}+\log{n}\log^{\epsilon}{r}\right)\right)$
time algorithm for this problem, which is the first improvement to date over
FR-Dijkstra for the important case when $r$ is polynomial in $n$. In this case,
our algorithm is faster by a factor of $O(\log^2{\log{n}})$ and implies
improved upper bounds for such planar graph problems as multiple-source
multiple-sink maximum flow, single-source all-sinks maximum flow, and (dynamic)
exact distance oracles.

2
The categories of this paper are: math
0
The categories of this paper are: hep-ph
29
The categories of this paper are: funct-an
17
The categories of this paper are: q-fin
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
27
The categories of this paper are: comp-gas
8
The categories of this paper are: hep-ex
26
The categories of this paper are: bayes-an
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
21
The categories of this paper are: adap-org
24
The categories of this paper are: dg-ga
11
The categories of this paper are: hep-lat
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc