License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.7
URN: urn:nbn:de:0030-drops-83001
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8300/
Eden, Talya ;
Rosenbaum, Will
On Sampling Edges Almost Uniformly
Abstract
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.
BibTeX - Entry
@InProceedings{eden_et_al:OASIcs:2018:8300,
author = {Talya Eden and Will Rosenbaum},
title = {{On Sampling Edges Almost Uniformly}},
booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)},
pages = {7:1--7:9},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-064-4},
ISSN = {2190-6807},
year = {2018},
volume = {61},
editor = {Raimund Seidel},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8300},
URN = {urn:nbn:de:0030-drops-83001},
doi = {10.4230/OASIcs.SOSA.2018.7},
annote = {Keywords: Sublinear Algorithms, Graph Algorithms, Sampling Edges, Query Complexity}
}
|
Keywords: |
|
Sublinear Algorithms, Graph Algorithms, Sampling Edges, Query Complexity |
|
Collection: |
|
1st Symposium on Simplicity in Algorithms (SOSA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.01.2018 |
