Sampling an Edge in Sublinear Time Exactly and Optimally

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Sampling an Edge in Sublinear Time Exactly and Optimally. / Eden, Talya; Narayanan, Shyam; Tětek, Jakub.

Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). ed. / Telikepalli Kavitha; Kurt Mehlhorn. Society for Industrial and Applied Mathematics, 2023. p. 253-260.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Eden, T, Narayanan, S & Tětek, J 2023, Sampling an Edge in Sublinear Time Exactly and Optimally. in T Kavitha & K Mehlhorn (eds), Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, pp. 253-260. https://doi.org/10.1137/1.9781611977585.ch23

APA

Eden, T., Narayanan, S., & Tětek, J. (2023). Sampling an Edge in Sublinear Time Exactly and Optimally. In T. Kavitha, & K. Mehlhorn (Eds.), Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA) (pp. 253-260). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977585.ch23

Vancouver

Eden T, Narayanan S, Tětek J. Sampling an Edge in Sublinear Time Exactly and Optimally. In Kavitha T, Mehlhorn K, editors, Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics. 2023. p. 253-260 https://doi.org/10.1137/1.9781611977585.ch23

Author

Eden, Talya ; Narayanan, Shyam ; Tětek, Jakub. / Sampling an Edge in Sublinear Time Exactly and Optimally. Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). editor / Telikepalli Kavitha ; Kurt Mehlhorn. Society for Industrial and Applied Mathematics, 2023. pp. 253-260

Bibtex

@inproceedings{92128f9df0f044e2adc724a5795eb011,
title = "Sampling an Edge in Sublinear Time Exactly and Optimally",
abstract = "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.",
author = "Talya Eden and Shyam Narayanan and Jakub T{\v e}tek",
year = "2023",
doi = "10.1137/1.9781611977585.ch23",
language = "English",
pages = "253--260",
editor = "Telikepalli Kavitha and Kurt Mehlhorn",
booktitle = "Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)",
publisher = "Society for Industrial and Applied Mathematics",
address = "United States",

}

RIS

TY - GEN

T1 - Sampling an Edge in Sublinear Time Exactly and Optimally

AU - Eden, Talya

AU - Narayanan, Shyam

AU - Tětek, Jakub

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

U2 - 10.1137/1.9781611977585.ch23

DO - 10.1137/1.9781611977585.ch23

M3 - Article in proceedings

SP - 253

EP - 260

BT - Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)

A2 - Kavitha, Telikepalli

A2 - Mehlhorn, Kurt

PB - Society for Industrial and Applied Mathematics

ER -

ID: 382686092