Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them by adding edges, with the goal to reduce the diameter of the graph. A long sequence of works has studied (efficient) shor...
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Article |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2602.10747 http://arxiv.org/abs/2602.10747 |
| Tags: |
Pas de tags, Soyez le premier à ajouter un tag!
|