论文标题
精确，最佳地在均方根时间中采样边缘
Sampling an Edge in Sublinear Time Exactly and Optimally
论文作者
论文摘要
从司额时间中的图中抽样边缘是一个基本问题，也是设计sublrinear-time算法的功能强大的子例程。假设我们可以访问图形的顶点，并且知道边缘数量的恒定因子近似值。 Eden and Rosenbaum [SOSA 2018]给出了Pointsise $ \ Varepsilon $ -Varepsilon $ -Appro-Appro-Appro-Approximate Edge采样$（N/\ SQRT {\ varepsilon m}）$。 TěTek和Thorup [Stoc 2022]随后将其改进到$ O（n \ log（\ varepsilon^{ - 1}）/\ sqrt {m}）$。同时，$ω（n/\ sqrt {m}）$时间是必要的。我们通过给出具有复杂性$ o（n/\ sqrt {m}）$的算法来解决问题，以完全均匀地采样边缘。
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 $\varepsilon$-approximate edge sampling with complexity $O(n/\sqrt{\varepsilon m})$ has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by Tětek and Thorup [STOC 2022] to $O(n \log(\varepsilon^{-1})/\sqrt{m})$. At the same time, $Ω(n/\sqrt{m})$ time is necessary. We close the problem, by giving an algorithm with complexity $O(n/\sqrt{m})$ for the task of sampling an edge exactly uniformly.
