research
∙
03/13/2023
Finding Diverse Minimum s-t Cuts
Recently, many studies have been devoted to finding diverse solutions in...
share
research
∙
02/24/2023
k-Center Clustering with Outliers in the MPC and Streaming Model
Given a point set P ⊆ X of size n in a metric space (X,dist) of doubling...
research
∙
10/11/2022
A Note on Reachability and Distance Oracles for Transmission Graphs
Let P be a set of n points in the plane, where each point p∈ P has a tra...
research
∙
08/16/2022
Computing Smallest Convex Intersecting Polygons
A polygon C is an intersecting polygon for a set O of objects in the pla...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
research
∙
04/04/2022
Partitioning axis-parallel lines in 3D
Let L be a set of n axis-parallel lines in ℝ^3. We are are interested in...
research
∙
03/14/2022
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
We consider the following surveillance problem: Given a set P of n sites...
research
∙
12/10/2021
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
Let P be a set of points in ℝ^d, where each point p∈ P has an associated...
research
∙
09/24/2021
k-Center Clustering with Outliers in the Sliding-Window Model
The k-center problem for a point set P asks for a collection of k congru...
research
∙
09/20/2021
Clique-Based Separators for Geometric Intersection Graphs
Let F be a set of n objects in the plane and let G(F) be its intersectio...
research
∙
09/15/2021
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model
We present subquadratic algorithms in the algebraic decision-tree model ...
research
∙
03/15/2021
Rectilinear Steiner Trees in Narrow Strips
A rectilinear Steiner tree for a set P of points in ℝ^2 is a tree that c...
research
∙
09/30/2020
The Online Broadcast Range-Assignment Problem
Let P={p_0,…,p_n-1} be a set of points in ℝ^d, modeling devices in a wir...
research
∙
05/05/2020
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
We consider the problem of finding patrol schedules for k robots to visi...
research
∙
03/22/2020
Euclidean TSP in Narrow Strip
We investigate how the complexity of Euclidean TSP for point sets P insi...
research
∙
03/17/2020
On beta-Plurality Points in Spatial Voting Games
Let V be a set of n points in ℝ^d, called voters. A point p∈ℝ^d is a plu...
research
∙
02/25/2019
On One-Round Discrete Voronoi Games
Let V be a multiset of n points in R^d, which we call voters, and let k≥...
research
∙
07/18/2018
An ETH-Tight Exact Algorithm for Euclidean TSP
We study exact algorithms for Euclidean TSP in R^d. In the early 1990s ...
research
∙
05/07/2018
Non-Monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces
It is well known that any set of n intervals in R^1 admits a non-monochr...
research
∙
03/28/2018
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
03/28/2018
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
09/29/2017
Dynamic Conflict-Free Colorings in the Plane
We study dynamic conflict-free colorings in the plane, where the goal is...
research
∙
09/15/2017
The Dominating Set Problem in Geometric Intersection Graphs
We study the parameterized complexity of dominating sets in geometric in...
research
∙
05/17/2017