Add to ORKGGiven a set S of n points in R"d, and a connected graph G having the points of S as its vertices, the stretch factor t* of G is defined as the maximal value is the length of a shortest path in G between p and q, and is the Euclidean distance between p and q. We show that an approximation to t* can be obtained by making O(n) approximate shortest path queries in the graph G. We apply this result to obtain efficient algorithms for approximating the stretch factor of Euclidean graphs such as paths, cycles, trees, planar graphs, and general graphs. The main idea behind the algorithm is to use Callahan and Kosaraju's well-separated pair decomposition. (orig.)SIGLEAvailable from TIB Hannover: RR 4485(1999,16) / FIZ - Fachinformationszzentrum ...
A standard way to approximate the distance between two vertices p and q in a graph is to compute a s...
Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(...
A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance b...
Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two ...
Abstract. Let G be a geometric graph whose vertex set S is a set of n points in Rd. The stretch fact...
Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) o...
Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shor...
Spanning trees have always been of great interest in various areas of com-puter science. The same is...
Abstract. In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio be...
length is at most t times the distance between u and v in the graph. We consider the problem of find...
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the probl...
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional si...
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the to...
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in whi...
Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie with...
A standard way to approximate the distance between two vertices p and q in a graph is to compute a s...
Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(...
A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance b...
Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two ...
Abstract. Let G be a geometric graph whose vertex set S is a set of n points in Rd. The stretch fact...
Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) o...
Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shor...
Spanning trees have always been of great interest in various areas of com-puter science. The same is...
Abstract. In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio be...
length is at most t times the distance between u and v in the graph. We consider the problem of find...
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the probl...
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional si...
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the to...
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in whi...
Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie with...
A standard way to approximate the distance between two vertices p and q in a graph is to compute a s...
Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(...
A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance b...