Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.

Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova

Browse the full SODA paper archive.