10 papers
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 …
Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
Eunjin Oh, Seongbin Park, Chanho Song
In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets in a metric spac…
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 (…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
Seongbin Park, Eunjin Oh
In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets with , the goal is t…
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…
Sparse Outerstring Graphs Have Logarithmic Treewidth
Shinwoo An, Eunjin Oh, Jie Xue
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with vertices has…
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…