New Streaming Algorithms for Parameterized Maximal Matching & Beyond
New Streaming Algorithms for Parameterized Maximal Matching & Beyond
复制标题
用于参数化最大匹配的新流算法
DOI：
10.1145/2755573.2755618
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Morteza Monemizadeh
中科院分区：
文献类型：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Hossein Esfandiari;MohammadTaghi Hajiaghayi;Morteza Monemizadeh
最近在SODA'15 [2]上，我们通过参数化流的框架研究了最大匹配，在那里我们在没有最大匹配皮肤大小的承诺下寻求解决方案。在本文中，我们重新审视这个问题，并提供了一个更简单的算法。我们也能够将同样的技术应用于点线覆盖问题[3]。
Very recently at SODA'15 [2], we studied maximal matching via the framework ofparameterized streaming, where we sought solutions under the promise that no maximal matching exceedskin size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to thePoint Line Coverproblem [3].
参数化流：最大匹配和顶点覆盖
DOI：
10.1137/1.9781611973730.82
发表时间：
2015
期刊：
影响因子：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Mohammad Taghi Hajiaghayi;Morteza Monemizadeh
通讯作者：
Morteza Monemizadeh
非严格旋转栅门数据流的高效采样
DOI：
10.1016/j.tcs.2015.01.026
发表时间：
2013
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Neta Barkay;E. Porat;Bar Shalem
通讯作者：
Bar Shalem