Given a graph @math , @math , we wish to compute a spanning tree whose maximum vertex degree is as small as possible. Computing the exact optimal solution is known to be NP-hard, since it generalizes the Hamiltonian path problem. For the approximation version of this problem, a @math time algorithm that computes a spanning tree of degree at most @math is previously known [F "urer, Raghavachari 1994]; here @math denotes the optimal tree degree. In this paper we give the first near-linear time algorithm for this problem. Specifically speaking, we first propose a simple @math time algorithm that achieves an @math approximation; then we further improve this algorithm to obtain a @math approximation in @math time.
Another variant is minimum degree Steiner trees which is related to network broadcasting @cite_12 @cite_3 @cite_11 . For undirected graphs, authors of @cite_1 showed that the same approximation guarantee and running time can be achieved as with minimum degree spanning trees in undirected graphs, i.e., a solution of tree degree @math and a running time of @math . For the directed case, @cite_11 showed that directed minimum degree Steiner trees problem cannot be approximated within @math unless @math , where @math is the set of terminals.
@cite_3 @cite_1 @cite_12 @cite_11
2104116126 2066700938 2069002708 2009976792
We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph @math and a root node @math , we seek a single spanning tree @math of minimum stretch , where the stretch of @math is defined to be the maximum ratio, over all terminal sets @math , of the cost of the minimal sub-tree @math of @math that connects @math to @math to the cost of an optimal Steiner tree connecting @math to @math in @math . Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time UST construction for general graphs with @math -stretch. We also give a polynomial time polylogarithmic-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first sub polynomial-stretch ( @math for any @math ) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs. Abstract The problem of constructing a spanning tree for a graph G = ( V , E ) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D ⊆ V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D . Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time. Abstract In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STPMSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5. We give the first nontrivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing. For both problems, the best ratios known before our work were the trivial O(k)-approximations. For the directed Steiner tree problem, we design a family of algorithms that achieves an approximation ratio of i(i?1)k1 i in time O(nik2i) for any fixed i1, where k is the number of terminals. Thus, an O(k?) approximation ratio can be achieved in polynomial time for any fixed ?0. Setting i=logk, we obtain an O(log2k) approximation ratio in quasi-polynomial time. For the directed generalized Steiner network problem we give an algorithm that achieves an approximation ratio of O(k2 3log1 3k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem, the set TSP problem, and several others in both directed and undirected graphs can be reduced in an approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain the first nontrivial approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate.