A tree cover of a metric space @math is a collection of trees, so that every pair @math has a low distortion path in one of the trees. If it has the stronger property that every point @math has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. Tree covers and Ramsey tree covers have been studied by BLMN03,GKR04,CGMZ05,GHR06,MN07 , and have found several important algorithmic applications, e.g. routing and distance oracles. The union of trees in a tree cover also serves as a special type of spanner, that can be decomposed into a few trees with low distortion paths contained in a single tree; Such spanners for Euclidean pointsets were presented by ADMSS95 . In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.
In the context of spanning trees, the problem of computing a spanning tree with low average stretch was first studied by @cite_11 . Following @cite_46 , @cite_2 @cite_42 obtained a nearly tight @math bound.
@cite_46 @cite_42 @cite_2 @cite_11
2046709864 2066700938 2031671531 2897842022
We study approaches for the exact solution of the NP-hard minimum spanning tree problem under conflict constraints. Given a graph (G(V,E) ) and a set (C E E ) of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in (C ). The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph ( G (E,C) ), where stable sets correspond to conflict-free subsets of (E ). We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates. 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. The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics -- Euclidean, rectilinear, and @math . By employing a subroutine that solves the post office problem, we show that, for fixed k @math 3, such a minimum spanning tree can be found in time O( @math ), where a(k) = @math . The bound can be improved to O( @math ) for points in the 3-dimensional Euclidean space. We also obtain o( @math ) algorithms for finding a farthest pair in a set of n points and for other related problems. The tree (t^* )-spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree (t^* )-spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem.