Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
METADATA ONLY
Loading...
Author / Producer
Date
2023-06-02
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only logO(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.
Permanent link
Publication status
published
External links
Book title
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
321 - 334
Publisher
Association for Computing Machinery
Event
55th Annual ACM Symposium on Theory of Computing (STOC '23)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
parallel algorithms; distributed algorithms; bfs; shortest path; exact distances; approximate distances
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
08730 - Gruppe Häupler / Group Häupler
Notes
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
184735 - Distributed Algorithms for Global Graph Problems (SNF)
184735 - Distributed Algorithms for Global Graph Problems (SNF)