when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-83001
URL:

;

### On Sampling Edges Almost Uniformly

 pdf-format:

### 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},
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 Seminar: 1st Symposium on Simplicity in Algorithms (SOSA 2018) Issue date: 2018 Date of publication: 05.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy