Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Bounded Dijkstra (BD): Search Space Reduction for Expediting Shortest
  Path Subroutines   The shortest path (SP) and shortest paths tree (SPT) problems arise both as
direct applications and as subroutines of overlay algorithms solving more
complex problems such as the constrained shortest path (CSP) or the constrained
minimum Steiner tree (CMST) problems. Often, such algorithms do not use the
result of an SP subroutine if its total cost is greater than a given bound. For
example, for delay-constrained problems, paths resulting from a least-delay SP
run and whose delay is greater than the delay constraint of the original
problem are not used by the overlay algorithm to construct its solution. As a
result of the existence of these bounds, and because the Dijkstra SP algorithm
discovers paths in increasing order of cost, we can terminate the SP search
earlier, i.e., once it is known that paths with a greater total cost will not
be considered by the overlay algorithm. This early termination allows to reduce
the runtime of the SP subroutine, thereby reducing the runtime of the overlay
algorithm without impacting its final result. We refer to this adaptation of
Dijkstra for centralized implementations as bounded Dijkstra (BD). On the
example of CSP algorithms, we confirm the usefulness of BD by showing that it
can reduce the runtime of some algorithms by 75% on average.

6
The categories of this paper are: astro-ph
21
The categories of this paper are: adap-org
20
The categories of this paper are: acc-phys
34
The categories of this paper are: chem-ph
18
The categories of this paper are: econ
19
The categories of this paper are: eess
22
The categories of this paper are: chao-dyn
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph
13
The categories of this paper are: quant-ph
37
The categories of this paper are: supr-con
0
The categories of this paper are: hep-ph
4
The categories of this paper are: cond-mat
16
The categories of this paper are: stat
32
The categories of this paper are: atom-ph
3
The categories of this paper are: physics