Sampling an Edge in Sublinear Time Exactly and Optimally
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Accepteret manuskript, 333 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA) |
Redaktører | Telikepalli Kavitha, Kurt Mehlhorn |
Forlag | Society for Industrial and Applied Mathematics |
Publikationsdato | 2023 |
Sider | 253-260 |
ISBN (Elektronisk) | 978-1-61197-758-5 |
DOI | |
Status | Udgivet - 2023 |
ID: 382686092