2026-08-10T16:16:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8300 2024-03-06T10:30:16Z ddc:004 open_access

On Sampling Edges Almost Uniformly Eden, Talya Rosenbaum, Will Sublinear Algorithms Graph Algorithms Sampling Edges Query Complexity We consider the problem of sampling an edge almost uniformly from an unknown graph, G = (V, E). Access to the graph is provided via queries of the following types: (1) uniform vertex queries, (2) degree queries, and (3) neighbor queries. We describe a new simple algorithm that returns a random edge e in E using \tilde{O}(n/sqrt{eps m}) queries in expectation, such that each edge e is sampled with probability (1 +/- eps)/m. Here, n = |V| is the number of vertices, and m = |E| is the number of edges. Our algorithm is optimal in the sense that any algorithm that samples an edge from an almost-uniform distribution must perform Omega(n/sqrt{m}) queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Talya Eden and Will Rosenbaum 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.7 urn:nbn:de:0030-drops-83001 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode