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     

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).     

Three-person spanning tree games

There are many situations where allocation of costs among the users of a minimum spanning tree network is a problem of concern. In [1], formulation of this problem as a game theoretic model, spanning tree games, has been considered. It is well known that st games have nonempty cores. Many researchers have studied other solutions related to st games. In this paper, we study three-person st games. Various properties connected to the convexity or no-convexity, and τ-value is studied. A characterization of the core and geometric interpretation is given. In special cases, the nucleolus of the game is given.     

Stochastic spanning tree problem

The minimal spanning tree problem has been well studied and until now many efficient algorithms such as [5,6] have been proposed. This paper generalizes it toward a stochastic version, i.e., considers a stochastic spanning tree problem in which edge costs are not constant but random variables and its objective is to find an optimal spanning tree satisfying a certain chance constraint. This problem may be considered as a discrete version of P-model first introduced by Kataoka [4].First it is transformed into its deterministic equivalent problem P. Then, an auxiliary problem P(R) with a positive parameter R is defined. After clarifying close relations between P and P(R), this paper proposes a polynomial order algorithm fully utilizing P(R). Finally, more improvement of the algorithm and applicability of this type algorithm to other discrete stochastic programming problems are discussed.     

Minimum cost spanning tree games

We consider the problem of cost allocation among users of a minimum cost spanning tree network. It is formulated as a cooperative game in characteristic function form, referred to as a minimum cost spanning tree (m.c.s.t.) game. We show that the core of a m.c.s.t. game is never empty. In fact, a point in the core can be read directly from any minimum cost spanning tree graph associated with the problem. For m.c.s.t. games with efficient coalition structures we define and construct m.c.s.t. games on the components of the structure. We show that the core and the nucleolus of the original game are the cartesian products of the cores and the nucleoli, respectively, of the induced games on the components of the efficient coalition structure.This paper is a revision of [4].     

The minimum-area spanning tree problem

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set of n points in the plane, find a spanning tree of of minimum “area”, where the area of a spanning tree is the area of the union of the n−1 disks whose diameters are the edges in . We prove that the Euclidean minimum spanning tree of is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

Chance constrained bottleneck spanning tree problem

In this paper we consider a stochastic version of the bottleneck spanning tree in which edge costs are independent random variables. Our problem is to find an optimal spanning tree and optimal satisficing level of the chance constraint with respect to the bottleneck (maximum cost) edge of the spanning tree. The problem is first transformed into a deterministic equivalent problem. Then a subproblem in order to solve the problem is introduced and the close relation between these problems is clarified. Finally, based on the relation, polynomial time solution procedures to solve the problem are proposed under two special functions of satisficing level which are given as examples to be solved easily.     

Merge-proofness in minimum cost spanning tree problems

In the context of cost sharing in minimum cost spanning tree problems, we introduce a property called merge-proofness. This property says that no group of agents can be better off claiming to be a single node. We show that the sharing rule that assigns to each agent his own connection cost (the Bird rule) satisfies this property. Moreover, we provide a characterization of the Bird rule using merge-proofness.     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

On the probabilistic min spanning tree Problem

We study a probabilistic optimization model for min spanning tree, where any vertex v _i of the input-graph G(V, E) has some presence probability p _i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any G￠ í GG' subseteq G is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.     

The prize-collecting generalized minimum spanning tree problem

We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time, while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances.     

Constructing a spanning tree with many leaves

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least \frac25 \frac{2}{5} n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with [ \frac25 ·k + \frac215 ·k￠ ] \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] leaves.     

A spanning tree cohomology theory for links

In their recent preprint, Baldwin, Ozsváth and Szabó defined a twisted version (with coefficients in a Novikov ring) of a spectral sequence, previously defined by Ozsváth and Szabó, from Khovanov homology to Heegaard–Floer homology of the branched double cover along a link. In their preprint, they give a combinatorial interpretation of the _E3$E_3$-term of their spectral sequence. The main purpose of the present paper is to prove directly that this _E3$E_3$-term is a link invariant. We also give some concrete examples of computation of the invariant.     

Optimality conditions in preference-based spanning tree problems

Spanning tree problems defined in a preference-based environment are addressed. In this approach, optimality conditions for the minimum-weight spanning tree problem (MST) are generalized for use with other, more general preference orders. The main goal of this paper is to determine which properties of the preference relations are sufficient to assure that the set of ‘most-preferred’ trees is the set of spanning trees verifying the optimality conditions. Finally, algorithms for the construction of the set of spanning trees fulfilling the optimality conditions are designed, improving the methods in previous papers.     

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.