Sampling an Edge in Sublinear Time Exactly and Optimally
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Accepted author manuscript, 333 KB, PDF document
Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of the graph and know a constant-factor approximation to the number of edges. An algorithm for pointwise ε-approximate edge sampling with complexity has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by Tetek and Thorup [STOC 2022] to . At the same time, time is necessary. We close the problem, by giving an algorithm with complexity for the task of sampling an edge exactly uniformly.
Original language | English |
---|---|
Title of host publication | Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA) |
Editors | Telikepalli Kavitha, Kurt Mehlhorn |
Publisher | Society for Industrial and Applied Mathematics |
Publication date | 2023 |
Pages | 253-260 |
ISBN (Electronic) | 978-1-61197-758-5 |
DOIs | |
Publication status | Published - 2023 |
ID: 382686092