Sampling an Edge in Sublinear Time Exactly and Optimally

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationProceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)
EditorsTelikepalli Kavitha, Kurt Mehlhorn
PublisherSociety for Industrial and Applied Mathematics
Publication date2023
Pages253-260
ISBN (Electronic)978-1-61197-758-5
DOIs
Publication statusPublished - 2023

ID: 382686092