Spanner constructions focus on the initial design of the network. However, networks tend to
improve over time. In this paper, we focus on the improvement step. Given a graph and a …

We consider the problem of computing the diameter of a unicycle graph (ie, a graph with a
unique cycle). We present an O (n) time algorithm for the problem, where n is the number of …

We study the problem of augmenting a metric graph by adding k edges while minimizing the
radius of the augmented graph. We give a simple 3-approximation algorithm and show that …

In this thesis, we focus on two topics in computational geometry. The first topic is analysing
trajectory similarity. A trajectory tracks the movement of an object over time. A common way …

Let T be a tree with n vertices in a metric space. We consider the problem of adding one
shortcut edge to T to minimize the radius of the resulting graph. For the continuous version of …

Let P be a path graph of n vertices embedded in a metric space. We consider the problem of
adding a new edge to P so that the radius of the resulting graph is minimized, where any …

Abstract In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n
vertices as input. The tree is embedded in an unknown metric space and we have unlimited …

We consider the problem of augmenting an n-vertex tree with one shortcut in order to
minimize the diameter of the resulting graph. The tree is embedded in an unknown space …

요 약본 논문은 거리 공간 (metric space) 속에 포함된 그래프에서 각 간선의 가중치가 거리 공간
상의 두 끝 정점간의 거리로 주어지는 그래프를 다룬다. 특별히 우리는 이러한 그래프 중 개 …