On a proposed divide-and-conquer minimal spanning tree algorithm

In a recent paper published in this journal, R. Chang and R. Lee purport to devise anO(N logN) time minimal spanning tree algorithm forN points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound ofO(N ² logN). Since it is known that alternate, trulyO(N logN) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.This author's research is supported in part by the Washington State Technology Center and by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

Finding minimal spanning trees in a euclidean coordinate space

The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n ²) operations,n being the cardinality of the point set, are also given.     

On the isometric minimal immersion into a euclidean space

We study the volume growth of the geodesic balls of a minimal submanifold in a Euclidean space. A necessary condition for the isometric minimal immersion into a Euclidean space is obtained. A classification of non-positively curved minimal hypersurfaces in a Euclidean space is given. This work is partially supported by the National Science Foundation of China     

AnO(N logN) minimal spanning tree algorithm forN points in the plane

We shall present a divide-and-conquer algorithm to construct minimal spanning trees out of a set of points in two dimensions. This algorithm is based upon the concept of Voronoi diagrams. If implemented in parallel, its time complexity isO(N) and it requiresO(logN) processors whereN is the number of input points.This research was partially supported by the National Science Council of the Republic of China under the Grant NSC74-0408-E007-01.     

Structure of three-dimensional minimal parabolic surfaces in euclidean space

It is shown that the structure of a three-dimensional minimal parabolic surface is determined by the pair (V², γ), where V² is a minimal two-dimensional surface in Sⁿ and γ satisfies Δγ+2γ=0 (here Δ is the Laplace operator in ℝ⁴). It is also shown that the singularities of the surface are determined by zeros of γ. Bibliography: 9 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 234, 1996, pp. 20–38.     

The minimal spanning tree and the upper box dimension

We show that the -weight of an MST over points in a metric space with upper box dimension has a bound independent of if d$"> and does not have one if .

     

Random minimal spanning tree and percolation on the N-cube

The N-cube is a graph with 2^N vertices and N2^N−1 edges. Suppose independent uniform random edge weights are assigned and let T be the spanning tree of minimal (total) weight. Then the weight of T is asymptotic to N⁻¹2^N ∑^∞_i=1 i⁻³ as N→∞. Asymptotics are also given for the local structure of T and for the distribution of its kth largest edge weight, k fixed. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 63–82, 1998     

Simulated annealing algorithm for the robust spanning tree problem

This paper addresses the robust spanning tree problem with interval data, i.e. the case of classical minimum spanning tree problem when edge weights are not fixed but take their values from some intervals associated with edges. The problem consists of finding a spanning tree that minimizes so-called robust deviation, i.e. deviation from an optimal solution under the worst case realization of interval weights. As it was proven in Kouvelis and Yu (Robust Discrete Optimization and Its Applications, Kluwer Academic, Norwell, 1997), the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated annealing, in order to calculate an approximate solution for large scale instances efficiently. We describe theoretical aspects and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop a metaheuristic approach for solving the robust spanning tree problem.     

On spanning tree congestion

We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge cut defined in G by the vertex sets of the two components of T−e contains at most edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226).     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.     

Finiteness of the number of ends of minimal submanifolds in euclidean space

We prove a version of the well-known Denjoy-Ahlfors theorem about the number of asymptotic values of an entire function for properly immersed minimal surfaces of arbitrary codimension in ℝ ^N . The finiteness of the number of ends is proved for minimal submanifolds with finite projective volume. We show, as a corollary, that a minimal surface of codimensionn meeting anyn-plane passing through the origin in at mostk points has no morec(n, N)k ends.     

On a minimal complex norm that extends the real euclidean norm

A minimal extension of the real euclidean norm to ⁿ is introduced and some complex analytic properties of its unit ball are studied.Research supported partially by Fulbright Grant (1986–1987) at Universität Osnabrück-Abteilung Vechta.     

A characterization of the folk rule for multi-source minimal cost spanning tree problems

In this paper we provide an axiomatic characterization of the folk rule for minimum cost spanning tree problems with multiple sources. The properties we need are: cone-wise additivity, cost monotonicity, symmetry, isolated agents, and equal treatment of source costs.     

A GRASP algorithm for the multi-criteria minimum spanning tree problem

This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.     

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.     

An efficient parallel algorithm for shifting the root of a depth first spanning tree

Given a simple, connected, undirected graph G on n vertices and a depth first spanning tree (dfst) T of G with root t, the root-shifting problem is to find a dfst R of G with a specified root r. We present an O(log n) step algorithm for solving this problem using n³ processors on a parallel computer which does not permit concurrent writes but allows concurrent reads. We also discuss a processor allocation strategy for this algorithm which can be implemented without increasing the overall running time of the algorithm.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.