Finding Graph Matchings in Data Streams
Finding Graph Matchings in Data Streams
复制标题
DOI：
10.1007/11538462_15
复制
发表时间：
2005-08
影响因子：
5.2
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
A. Mcgregor
我们提出的算法，发现大型图匹配的流模型。在这个模型中，适用于处理大量的图形，边缘以任意顺序流入，而不是驻留在随机访问的内存中。当ε> 0时，我们得到了最大基数匹配的近似和最大加权匹配的近似.这两种算法都使用恒定的传递次数和空间。
We present algorithms for finding large graph matchings in the streaming model. In this model, applicable when dealing with massive graphs, edges are streamed-in in some arbitrary order rather than residing in randomly accessible memory. Forε> 0, we achieve aapproximation for maximum cardinality matching and aapproximation to maximum weighted matching. Both algorithms use a constant number of passes andspace.