R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, and M. Monemizadeh. New streaming algorithms for parameterized maximal matching & beyond. In Symposium on Parallelism in Algorithms, pages 56-58, 2015.

Very recently at SODA'15, 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.

[ bib | .pdf ] Back

This file was generated by bibtex2html 1.92.