Can I read New Streaming Algorithms for Parameterized Maximal Matching & Beyond on EtoBox?

New Streaming Algorithms for Parameterized Maximal Matching & Beyond by Rajesh Chitnis; Graham Cormode; Hossein Esfandiari; MohammadTaghi Hajiaghayi; Morteza Monemizadeh is a scholarly article available to read on EtoBox.

What is New Streaming Algorithms for Parameterized Maximal Matching & Beyond about?

Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in 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 the Point Line Cover problem [3].

Author

Rajesh Chitnis; Graham Cormode; Hossein Esfandiari; MohammadTaghi Hajiaghayi; Morteza Monemizadeh

Publisher

ACM

Published

2015

Language

EN