Главная
Study mode:
on
1
Intro
2
Single Source Shortest Paths for Directed Graphs
3
Parallel Shortest Paths - Hopsets
4
Hopset: Definition
5
Inexact hopset example
6
Previous Results for Hopsets
7
Goal
8
Algorithm Preliminaries
9
The Algorithm for distance guess d
10
Path Related Nodes
11
Progress with recursion
12
Bridge nodes
13
Pivots and shortcutters
14
Distance limited search
15
Decrease search distance
16
Far bridge pivots
17
Conclusion
Description:
Explore the intricacies of directed hopsets and parallel approximate shortest paths in this 21-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the challenges of single-source shortest paths for directed graphs and discover how hopsets can be utilized to solve parallel shortest path problems. Learn about the definition and examples of inexact hopsets, previous research results, and the goals of the presented algorithm. Gain insights into algorithm preliminaries, path-related nodes, and the concept of bridge nodes. Understand the roles of pivots and shortcutters in distance-limited searches, and how to decrease search distances effectively. Conclude with an examination of far bridge pivots and their impact on efficient construction of directed hopsets.

Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths

Association for Computing Machinery (ACM)
Add to list