13 citations · 26 across the 5 of their papers we have counts for
6 papers
-Center Clustering with Outliers in the Sliding-Window Model
Mark de Berg, Morteza Monemizadeh, Yu Zhong
The -center problem for a point set~ asks for a collection of congruent balls (that is, balls of equal radius) that together cover all the points in and whose radius…
Clique-Based Separators for Geometric Intersection Graphs
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh +1
Let be a set of objects in the plane and let be its intersection graph. A balanced clique-based separator of is a set consisting of cliques whose removal…
Dynamic Maximal Independent Set
Morteza Monemizadeh
Given a stream of insertions and deletions of edges of an underlying graph (with fixed vertex set where is the number of vertices of ), we propose…
Testable Bounded Degree Graph Properties Are Random Order Streamable
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degre…
Kernelization via Sampling with Applications to Dynamic Graph Streams
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari +4
In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input…
A Unified Approach for Clustering Problems on Sliding Windows
Vladimir Braverman, Harry Lang, Keith Levin +1
We explore clustering problems in the streaming sliding window model in both general metric spaces and Euclidean space. We present the first polylogarithmic space -approximat…