Edge Estimation with Independent Set Oracles
Edge Estimation with Independent Set Oracles
复制标题
使用独立集预言机进行边缘估计
DOI：
10.1145/3404867
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Makrand Sinha
中科院分区：
文献类型：
--
作者：
P. Beame;Sariel Har;Sivaramakrishnan Natarajan Ramamoorthy;Cyrus Rashtchian;Makrand Sinha
我们研究了估计图中边数的任务，其中对图的访问是通过一个独立的集合预言来提供的。独立集查询从分组测试中获得动力，并应用于复杂的决策与计数问题。利用(I)PolyLog(N)二部独立集查询或(Ii)n2/3 PolyLog(N)独立集查询，给出了估计n-顶点图中边数的两种算法。
We study the task of estimating the number of edges in a graph, where the access to the graph is provided via an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an n-vertex graph, using (i) polylog(n) bipartite independent set queries or (ii) n2/3 polylog(n) independent set queries.
使用独立集查询进行近乎最优的边缘估计
DOI：
10.1137/1.9781611975994.177
发表时间：
2020
期刊：
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chen, Xi;Levi, Amit;Waingarten, Erik
通讯作者：
Waingarten, Erik
通过边缘采样计算星子图的次线性时间算法
影响因子：
1.1
作者：
Aliakbarpour, Maryam;Biswas, Amartya Shankha;Gouleakis, Themis;Peebles, John;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak