Sublinear-Time Algorithms for Approximating Graph Parameters
Sublinear-Time Algorithms for Approximating Graph Parameters
复制标题
用于近似图参数的次线性时间算法
DOI：
10.1007/978-3-319-91908-9_7
复制
发表时间：
2019
期刊：
影响因子：
1.9
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
D. Ron
给定一个图\（G=（V，E）\），我们可能对计算与该图相关的各种参数感兴趣。这些参数包括平均度、连通分量的数量和最小顶点覆盖的大小。这些参数和许多其他参数可以以有效的方式（精确地或近似地）计算。也就是说，在时间上，它在图的大小上是多项式的，甚至可能在这个大小上是线性的。然而，对于非常大的图，即使是线性时间也可能是不可行的。因此，我们需要设计更有效的算法，即在次线性时间内运行的算法。
Given a graph \(G=(V,E)\), we may be interested in computing various parameters that are associated with the graph. Such parameters include the average degree, the number of connected components, and the size of a minimum vertex cover. These parameters and many others can be computed (exactly or approximately) in an efficient manner. That is, in time that is polynomial in the size of the graph, and possibly even linear in this size. However, for very large graphs, even linear time may by infeasible. Hence, we need to design more efficient algorithms, that is, algorithms that run in sublinear time.