On Steiner minimal trees withLp distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ –x ₂¦ ^p + ¦y₁ –y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio _p to be inf{L _s (P)/L _m (P)¦PL _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ₁ = 2/3. Chung and Graham proved ₂ > 0.842. We prove in this paper that {} = 2/3 and (2/2)_{12 p} 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of “backtracking” and “branch-and-bound.” Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible. We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd ≥ 3, but it is probably true whend = 2.) The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision ?. We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision ?, then there is an (N/?)^O(√N)-time algorithm, which is subexponential if 1/? grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(√N) time. J. S. Provan devised an O(N ⁶/?⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of “Steiner sensitivity diagrams” is correct. All of these algorithms are for a “real RAM” model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths ≤ (1 + ?) × optimum, where ? is arbitrarily small, are considered here.     

Steiner minimal trees for a class of zigzag lines

Sets of points for which the Steiner minimal tree is known, are available only for some very special cases. This paper describes the Steiner minimal tree for a set of points forming the vertices of special zigzag lines.     

Steiner minimal trees for a class of zigzag lines

Sets of points for which the Steiner minimal tree is known, are available only for some very special cases. This paper describes the Steiner minimal tree for a set of points forming the vertices of special zigzag lines.     

Exact computation of Steiner minimal trees in the plane

A Steiner Minimal Tree (SMT) for a given set A = {a₁, …, a_n} in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besides a₁, …, a_n. Computer programs for SMTs are exponential and have so far only been able to solve, in a reasonable time, problems with n ⩽ 15. We present improvements to an algorithm of Winter (1981), which enable us to solve all 17-point problems and an estimated 80% of all randomly generated problems with n⩽ 30.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

On the location of Steiner points in uniformly-oriented Steiner trees

We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m?1.     

A fast algorithm for Steiner trees

Summary Given an undirected distance graph G=(V, E, d) and a set S, where V is the set of vertices in G, E is the set of edges in G, d is a distance function which maps E into the set of nonnegative numbers and SV is a subset of the vertices of V, the Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. In this paper, we analyze a heuristic algorithm for the Steiner tree problem. The heuristic algorithm has a worst case time complexity of O(¦S¦¦V¦ ²) on a random access computer and it guarantees to output a tree that spans S with total distance on its edges no more than 2(1–1/l) times that of the optimal tree, where l is the number of leaves in the optimal tree.     

On bicriterion minimal spanning trees: An approximation

In this paper we focus on the problem of computing the set of efficient spanning trees for a given network where each arc carries two attributes. This problem is -complete. We discuss two heuristics, namely, neighbourhood search (which is a well-known method) and adjacent search, a new method. They both approximate the set of efficient spanning trees. The difference lies in which kind of spanning trees are generated in each iteration. For neighbourhood search, all spanning trees which are adjacent to at least one spanning tree in the current approximation set are considered. Adjacent search is similar to neighbourhood search except that only spanning trees which are adjacent to at least two spanning trees in the current approximation set are considered. Based on computational results it is concluded that adjacent search is a reasonable alternative to neighbourhood search, especially for large problems.     

Steiner trees in uniformly quasi-bipartite graphs

The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance ratio. As all instances resulting from known lower bound reductions are uniformly quasi-bipartite, it is interesting whether this special case can be approximated better than the general case. We present an approximation algorithm with performance ratio 73/60<1.217 for the uniformly quasi-bipartite case. This improves on the previously known ratio of 1.279 of Robins and Zelikovsky. We use a new method of analysis that combines ideas from the greedy algorithm for set cover with a matroid-style exchange argument to model the connectivity constraint. As a consequence, we are able to provide a tight instance.     

Searching Steiner trees for web graph query

The enormous growth in information technology has revolutionized the way people can access information sources. Web search engines have played an important role to support what the user wants precisely and efficiently from the vast web database. Different from conventional search engine approaches, searching the structure of the web, where the answer comprises more than a single page connected by hyperlinks, needs to be meritoriously developed. We propose Linear Programming models in order to generate the optimal structured web objects searching for relevant web graphs. In the model, the web objects with node and edge weights that represent the ranking measures for Webpages and hyperlinks are devised to rank the relevance in terms of keyword vectors. We also developed a tree-filtering algorithm and top-k Steiner tree algorithm that is used to provide the search recommendations in practical applications. With real web databases, the experimental study shows that the LP approach outperforms the conventional search engines with respect to execution time and quality of results.     

Comments on Bern's probabilistic results on rectilinear Steiner trees

It is shown that Bern's probabilistic asymptotic results on rectilinear Steiner trees remain valid for the model that there are exactlyN nodes uniformly distributed in a square of side N.     

Prize collecting Steiner trees with node degree dependent costs

We discuss a variant of the prize-collecting Steiner tree problem with node degree dependent costs using a telecommunications setting to motivate these costs. We present and test models which are tailored for this variant of the problem. Results taken from instances with up to 100 nodes are used to evaluate the quality of the proposed models for solving the problem, as well as, in terms of the correspondent linear programming relaxation.     

Reoptimization of Steiner trees: Changing the terminal set

Given an instance of the Steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. In this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. Our results are as follows: (i) We prove that these reoptimization variants of the Steiner tree problem are NP-hard, even if edge costs are restricted to values from {1,2}$\{1,2\}$. (ii) We design 1.5-approximation algorithms for both variants of local modifications. This is an improvement over the currently best known approximation algorithm for the classical Steiner tree problem which achieves an approximation ratio of 1+ln(3)/2≈1.55$1+ln\left(3\right)/2\approx 1.55$. (iii) We present a PTAS for the subproblem in which the edge costs are natural numbers {1,…,k}$\{1,\dots ,k\}$ for some constant k$k$.     

Comments on Bern's probabilistic results on rectilinear Steiner trees

It is shown that Bern's probabilistic asymptotic results on rectilinear Steiner trees remain valid for the model that there are exactlyN nodes uniformly distributed in a square of side √N.     

On the longest path algorithm for reconstructing trees from distance matrices

Culberson and Rudnicki [J.C. Culberson, P. Rudnicki, A fast algorithm for constructing trees from distance matrices, Inform. Process. Lett. 30 (4) (1989) 215-220] gave an algorithm that reconstructs a degree d restricted tree from its distance matrix. According to their analysis, it runs in time O(dnlogdn) for topological trees. However, this turns out to be false; we show that the algorithm takes time in the topological case, giving tight examples.     

Algorithms for updating minimal spanning trees

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n²) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing4 (1975), 375–380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n²) steps. If all the vertices are considered, O(n³) steps may be used. The algorithm which we present here takes only O(n²) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge.