5 papers · 1 filter
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
Sujoy Bhore, Arnold Filter, Eunjin Oh +2
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 …
DAG Covers for Structured Graphs: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,v…
Single-Source Shortest Path Problem in Weighted Disk Graphs
Shinwoo An, Eunjin Oh, Jie Xue
In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in t…
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…
ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
Shinwoo An, Eunjin Oh
In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set o…