Bipartite Graph Matchings in the Semi-streaming Model
Bipartite Graph Matchings in the Semi-streaming Model
复制标题
半流模型中的二部图匹配
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Anand Srivastav
中科院分区：
文献类型：
--
作者：
Sebastian Eggert;Lasse Kliemann;Anand Srivastav
我们提出了一种在半流模型中的两部分图中找到大匹配的算法，在此模型中，输入图G =（V，e）在某个任意顺序中表示为其边缘的流动该算法由o（n，polygog n）位界定，其中n = | v |。 use（o {（（{frac {1} {epsilon}）^8}）}））））））通过输入流。 }））（McGregor 2005）。
We present an algorithm for finding a large matching in a bipartite graph in the semi-streaming model. In this model, the input graph G = (V, E) is represented as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(n , polylog n) bits, where n = |V|. For e> 0, our algorithm finds a (frac{1}{1+epsilon})-approximation of a maximum-cardinality matching and uses (O{({(frac{1}{epsilon})^8})}) passes over the input stream. The only previously known algorithm with such arbitrarily good approximation – though for general graphs – required exponentially many (Omega({{(frac{1}{epsilon})^{frac{1}{epsilon}}}})) passes (McGregor 2005).