research
∙
03/02/2023
Geometric Spanning Trees Minimizing the Wiener Index
The Wiener index of a network, introduced by the chemist Harry Wiener, i...
share
research
∙
02/21/2023
Dynamic Euclidean Bottleneck Matching
A fundamental question in computational geometry is for a set of input p...
research
∙
09/22/2022
Piercing Diametral Disks Induced by Edges of Maximum Spanning Tree
Let P be a set of points in the plane and let T be a maximum-weight span...
research
∙
12/11/2021
Piercing Pairwise Intersecting Geodesic Disks by Five Points
Given a simple polygon P on n vertices, and a set D of m pairwise inters...
research
∙
05/05/2021
2× n Grids have Unbounded Anagram-Free Chromatic Number
We show that anagram-free vertex colouring a 2× n square grid requires a...
research
∙
12/10/2020
A Linear-Time Algorithm for Minimum k-Hop Dominating Set of a Cactus Graph
Given a graph G=(V,E) and an integer k ≥ 1, a k-hop dominating set D of ...
research
∙
04/20/2020
Parameterized Study of Steiner Tree on Unit Disk Graphs
We study the Steiner Tree problem on unit disk graphs. Given a n vertex ...
research
∙
04/19/2020
Planar Bichromatic Bottleneck Spanning Trees
Given a set P of n red and blue points in the plane, a planar bichromati...
research
∙
04/19/2020
Minimizing Total Interference in Asymmetric Sensor Networks
The problem of computing a connected network with minimum interference i...
research
∙
03/17/2019
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
A graph G with n vertices is called an outerstring graph if it has an in...
research
∙
12/24/2018
Near-Optimal O(k)-Robust Geometric Spanners
For any constants d> 1, ϵ >0, t>1, and any n-point set P⊂R^d, we show th...
research
∙
12/17/2018
Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
research
∙
10/22/2018
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
research
∙
09/26/2018
Approximability of Covering Cells with Line Segments
In COCOA 2015, Korman et al. studied the following geometric covering pr...
research
∙
03/28/2018
Boundary Labeling for Rectangular Diagrams
Given a set of n points (sites) inside a rectangle R and n points (label...
research
∙
03/09/2018
Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
research
∙
02/26/2018
Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
research
∙
10/02/2017
Network Optimization on Partitioned Pairs of Points
Given n pairs of points, S = {{p_1, q_1}, {p_2, q_2}, ..., {p_n, q_n}}, ...
research
∙
09/08/2017
