Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-δ minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most δ. The problem is NP-hard for 2≤δ≤3, while the NP-hardness of the problem is open for δ=4. The problem is polynomial-time solvable when δ=5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most times the weight of an MST.     

Low-degree minimum spanning trees

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that, under theL _p norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitraryL _p metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the rectilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear space the maximum possible degree of a minimum-degree MST is either 13 or 14. Gabriel Robins was partially supported by NSF Young Investigator Award MIP-9457412. Jeffrey Salowe was partially supported by NSF Grants MIP-9107717 and CCR-9224789.     

On generalized minimum spanning trees

The generalized minimum spanning tree problem consists of designing a minimum cost tree spanning several clusters. The purpose of this note is to pinpoint several inaccuracies contained in a previous publication and to propose a valid formulation for this problem.     

On Steiner trees and minimum spanning trees in hypergraphs

The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.     

Transitions in geometric minimum spanning trees

We study some combinatorial and algorithmic problems associated with an arbitrary motion of input points in space. The motivation for such an investigation comes from two different sources:computer modeling andsensitivity analysis. In modeling, the dynamics enters the picture since geometric objects often model physical entities whose positions can change over time. In sensitivity analysis, the motion of the input points might represent uncertainties in the precise location of objects. The main results of the paper deal with state transitions in the minimum spanning tree when one or more of the input points move arbitrarily in space. In particular, questions of the following form are addressed: (i) How many different minimum spanning trees can arise if one point moves while the others remain fixed? (ii) When does the minimum spanning tree change its topology if all points are allowed to move arbitrarily?     

On random minimum length spanning trees

We extend and strengthen the result that, in the complete graphK _n with independent random edge-lengths uniformly distributed on [0, 1], the expected length of the minimum spanning tree tends to(3) asn. In particular, ifK _n is replaced by the complete bipartite graphK _{n, n} then there is a corresponding limit of 2 (3).     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

Average distance,minimum degree,and spanning trees

The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

A parallel algorithm for constructing minimum spanning trees

The construction of minimum spanning trees (MSTs) of weighted graphs is a problem that arises in many applications. In this paper we will study a new parallel algorithm that constructs an MST of an N-node graph in time proportional to N lg N, on an $\text{N}\text{(}\text{lg}\text{N)-}\text{processor}$ computing system. The primary theoretical contribution of this paper is the new algorithm, which is an improvement over Sollin's parallel MST algorithm in several ways. On a more practical level, this algorithm is appropriate for implementation in VLSI technology.     

Maximizing the minimum voter satisfaction on spanning trees

This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, can be determined efficiently given the goal of maximin voter satisfaction. In particular, we show that computing spanning trees for maximin voter satisfaction under voting rules such as approval voting or the Borda count is -complete for a variable number of voters whereas it remains polynomially solvable for a constant number of voters.     

The traveling-salesman problem and minimum spanning trees: Part II

The relationship between the symmetric traveling-salesman problem and the minimum spanning tree problem yields a sharp lower bound on the cost of an optimum tour. An efficient iterative method for approximating this bound closely from below is presented. A branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it, ranging in size up to sixty-four cities. The bounds used are so sharp that the search trees are minuscule compared to those normally encountered in combinatorial problems of this type.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.This research has been partially supported by the National Science Foundation under Grant GP-25081 with the University of California. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

On minimum and maximum spanning trees of linearly moving points

In this paper we investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Here, a transition means a change on the combinatorial structure of the spanning trees. Suppose that we are given a set ofn points ind-dimensional space,S={p ₁,p ₂, ...p _n }, and that all points move along different straight lines at different but fixed speeds, i.e., the position ofp _i is a linear function of a real parametert. We investigate the numbers of transitions of MinST and MaxST whent increases from-∞ to +∞. We assume that the dimensiond is a fixed constant. Since there areO(n ²) distances amongn points, there are naivelyO(n ⁴) transitions of MinST and MaxST. We improve these trivial upper bounds forL ₁ andL _∞ distance metrics. Letk _p (n) (resp. ) be the number of maximum possible transitions of MinST (resp. MaxST) inL _p metric forn linearly moving points. We give the following results in this paper: κ₁(n)=O(n ^5/2 α(n)),κ _∞(n)=O(n ^5/2 α(n)), , and where α(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., thec-oriented case in which there are onlyc distinct velocity vectors for movingn points, and the case in which onlyk points move.     

Dynamic Euclidean minimum spanning trees and extrema of binary functions

We maintain the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized timeO(n ^1/2 log² n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in timeO(n ^e ) per update. Our algorithm uses a novel construction, theordered nearest neighbor path of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of binary functions, including the diameter of a point set and the bichromatic farthest pair. This research was supported in part by NSF Grant CCR-9258355     

Maintaining dynamic minimum spanning trees: An experimental study

We report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al., sparsification on top of Frederickson’s algorithm, and other (less sophisticated) dynamic algorithms. In our experiments, we considered as test sets several random, semi-random and worst-case inputs previously considered in the literature together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems).