4 papers
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
Sujoy Bhore, Arnold Filtser, Arnold Filter +3
In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A -hash with diameter bound …
Fully Scalable MPC Algorithms for WSPD in Doubling and Euclidean Spaces
Eunjin Oh, Hyeonjun Shin
In this paper, we study the problem of constructing a -well-separated pair decomposition (WSPD) for a point set of size in the Massively Parallel Computation (…
Dynamic parameterized problems on unit disk graphs
Shinwoo An, Kyungjin Cho, Leo Jang +6
In this paper, we study fundamental parameterized problems such as -Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk…
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
Shinwoo An, Yeonsu Chang, Kyungjin Cho +4
Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Minimum Pre-assignment for Uniquificatio…