Sampling an Edge in Sublinear Time Exactly and Optimally
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Sampling an Edge in Sublinear Time Exactly and Optimally. / Eden, Talya; Narayanan, Shyam; Tětek, Jakub.
Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). ed. / Telikepalli Kavitha; Kurt Mehlhorn. Society for Industrial and Applied Mathematics, 2023. p. 253-260.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Sampling an Edge in Sublinear Time Exactly and Optimally
AU - Eden, Talya
AU - Narayanan, Shyam
AU - Tětek, Jakub
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
U2 - 10.1137/1.9781611977585.ch23
DO - 10.1137/1.9781611977585.ch23
M3 - Article in proceedings
SP - 253
EP - 260
BT - Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics
ER -
ID: 382686092