Sampling an Edge in Sublinear Time Exactly and Optimally

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfæ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.
OriginalsprogEngelsk
TitelProceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)
RedaktørerTelikepalli Kavitha, Kurt Mehlhorn
ForlagSociety for Industrial and Applied Mathematics
Publikationsdato2023
Sider253-260
ISBN (Elektronisk)978-1-61197-758-5
DOI
StatusUdgivet - 2023

ID: 382686092