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 sto...
详细信息
ISBN:
(纸本)9783642041273
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 = vertical bar V vertical bar. For epsilon > 0, our algorithm finds a 1/1+epsilon-approx.mation of a maximum-cardinality matching and uses O ((1/epsilon)(8)) passes over the input stream. The only previously known algorithm with such arbitrarily good approx.mation though for general graphs required exponentially many Omega ((1/epsilon)(1/epsilon))passes (McGregor 2005).
暂无评论