Add to ORKGGiven a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space
Abstract. In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio be...
AbstractLet G=(V,E) be an undirected graph with n vertices embedded in a metric space. We consider t...
The main contribution of this thesis is approximation algorithms for several computational geometry ...
Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shor...
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the probl...
We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the lar...
We augment a plane Euclidean network with a segment or shortcut to minimize the largest distance bet...
Given a set S of n points in R"d, and a connected graph G having the points of S as its vertice...
Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two ...
We study the problem of minimizing the diameter of a graph by adding k shortcut edges, for speeding ...
We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the large...
Abstract. Let G be a geometric graph whose vertex set S is a set of n points in Rd. The stretch fact...
An O(n log n)--time algorithm is presented that, when given a set S of n points in and an integer...
An O(n log n)-time algorithm is presented that, when given a set S of n points in R{double-struck} d...
Abstract. In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio be...
AbstractLet G=(V,E) be an undirected graph with n vertices embedded in a metric space. We consider t...
The main contribution of this thesis is approximation algorithms for several computational geometry ...
Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shor...
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the probl...
We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the lar...
We augment a plane Euclidean network with a segment or shortcut to minimize the largest distance bet...
Given a set S of n points in R"d, and a connected graph G having the points of S as its vertice...
Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two ...
We study the problem of minimizing the diameter of a graph by adding k shortcut edges, for speeding ...
We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the large...
Abstract. Let G be a geometric graph whose vertex set S is a set of n points in Rd. The stretch fact...
An O(n log n)--time algorithm is presented that, when given a set S of n points in and an integer...
An O(n log n)-time algorithm is presented that, when given a set S of n points in R{double-struck} d...
Abstract. In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio be...
AbstractLet G=(V,E) be an undirected graph with n vertices embedded in a metric space. We consider t...
The main contribution of this thesis is approximation algorithms for several computational geometry ...
