Metadata only
Date
2023Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We give a simple, local process for nodes in an undirected graph to form non-adjacent clusters that (1) have at most a polylogarithmic diameter and (2) contain at least half of all vertices.
Efficient1 deterministic distributed clustering algorithms for computing strong-diameter network decompositions and other key tools follow immediately. Overall, our process is a direct and drastically simplified way for computing these fundamental objects. Show more
Publication status
publishedExternal links
Book title
2023 Symposium on Simplicity in Algorithms (SOSA)Pages / Article No.
Publisher
SIAMEvent
Organisational unit
08730 - Gruppe Häupler / Group Häupler
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
184735 - Distributed Algorithms for Global Graph Problems (SNF)
Related publications and datasets
Is new version of: https://doi.org/10.48550/arXiv.2210.11784
More
Show all metadata
ETH Bibliography
yes
Altmetrics