English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce stronger notions for approximate single-source shortest-pathdistances, show how to efficiently compute them from weaker standard notions,and demonstrate the algorithmic power of these new notions and transformations.One application is the first work-efficient parallel algorithm for computingexact single-source shortest paths graphs -- resolving a major open problem inparallel computing.  Given a source vertex in a directed graph with polynomially-boundednonnegative integer lengths, the algorithm computes an exact shortest path treein $m \log^{O(1)} n$ work and $n^{1/2+o(1)}$ depth. Previously, no parallelalgorithm improving the trivial linear depths of Dijkstra's algorithm withoutsignificantly increasing the work was known, even for the case of undirectedand unweighted graphs (i.e., for computing a BFS-tree).  Our main result is a black-box transformation that uses $\log^{O(1)} n$standard approximate distance computations to produce approximate distanceswhich also satisfy the subtractive triangle inequality (up to a$(1+\varepsilon)$ factor) and even induce an exact shortest path tree in agraph with only slightly perturbed edge lengths. These strengthenedapproximations are algorithmically significantly more powerful and overcomewell-known and often encountered barriers for using approximate distances. Indirected graphs they can even be boosted to exact distances. This results in ablack-box transformation of any (parallel or distributed) algorithm forapproximate shortest paths in directed graphs into an algorithm computing exactdistances at essentially no cost. Applying this to the recent breakthroughs ofFineman et al. for compute approximate SSSP-distances via approximate hopsetsgives new parallel and distributed algorithm for exact shortest paths.

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances