在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例     

网络中一类最短支撑树的计算方法

本文在无向赋权图求最短路的Dijkstra算法的基础上,提出了在有向网络图中寻找具有一个枢纽点且与其它各点均有定向联系的最短支撑树的算法,同时还给出了应用该算法的一个计算实例。     

Pendants-median支撑树及其一个相关问题:复杂性和算法

The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3).     

带梯子的曲折线上的最短树问题

Abstract. In this paper,Steiner minimal trees for point sets with special structure are studied.These sets consist of zigzag lines and equidistant points lying on them.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

几类图的支撑树的个数

推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.     

约束四点集的最短网络问题

设Ｌ为Ｅｕｃｌｉｄｅａｎ平面上一连续曲线,在Ｌ的一侧有一个含ｎ个固定点的集合Ｎ,且点集Ｎ的凸包ＣＨ（Ｎ）与曲线ＬＩ 相交,总是是在Ｌ上找一点Ｐ,使点集Ｎ∪（Ｐ）的互联网络最短,本文在Ｌ是圆及点集Ｎ含有３个点的条件下给出了问题解。     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。     

计算最小支撑出树的一种简便算法

本文通过对网络中有向支撑出树性质的研究,提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一种较简便的计算方法,并给出了应用该算法进行实际操作的一个算例．     

可量词消去的带根节点的树理论

讨论了带根节点r的有向树、无向树理论的量词消去性质,找到决定理论量词消去的三类特殊公式,并给出了在语言■_0={E,r}(E为有向边或无向边)及添加二元距离关系D_(n,n)w所得膨胀语言下,可量词消去的这两类理论的完全分类.     

通讯网络中极小费用生成树的一种算法

针对具有n个通讯站的局域网络,运用增加或调整虚设站的方法,给出一种在混合距离下的极小费用生成树的算法.并就MCM91问题B,求出了极小费用生成树,其总费用小于美国马里兰州里斯勃来莱州立大学数学科学系B.A.Fusaro所提供的论文中的费用.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem

In this paper we propose a hybrid memory adaptive heuristic for solving the Capacitated Minimum Spanning Tree (CMST) problem. We augment the problem formulation with additional non-redundant constraints via use of adaptive memory, to improve upon the performance of an elementary heuristic (the Esau-Williams heuristic). Our methodology is tested against many of the previously reported heuristics for the CMST. We conclude that our generalized procedure performs on par with the best of these approaches in terms of solution quality, while expending a very modest amount of computational effort.     

Inapplicability of Asymptotic Results on the Minimal Spanning Tree in Statistical Testing

Penrose has given asymptotic results for the distribution of the longest edge of the minimal spanning tree and nearest neighbour graph for sets of multivariate uniformly or normally distributed points. We investigate the applicability of these results to samples of up to 100 points, in up to 10 dimensions. We conclude that the asymptotic results provide an acceptable approximation only in the uniform case. Their inaccuracy for the multivariate normal case means that they cannot be applied to improve Rohlf's gap test for an outlier in a set of multivariate data points, which depends on the longest edge of the minimal spanning tree of the set.     

Degree Conditions for Spanning Brooms

A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (E. Flandrin, T. Kaiser, R. Ku?el, H. Li and Z. Ryjá?ek, Neighborhood Unions and Extremal Spanning Trees, Discrete Math 308 (2008), 2343–2350) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order with , then G contains a spanning broom. This result is best possible.     

随机无穷点集上欧几里德最小扩张树的自包含性

本文证明好的欧氏空间无穷点集上最小扩张树的自包含性．应用上述性质,以及AlexanderK．S．[1]中有关二维Poisson连续渗流的结果,我们给出二维情形AldousD．和SteeleJ．M．[2]之猜想的一个新证明,区别于AlexanderK．S．[3]对上述猜想的排除法证明,我们直接证明它,显然,我们的证明更简单．对Poisson连续渗流,得到其二维临界值相对于Poisson最小扩张树的一个刻画;最后我们给出上述临界值相对于点渗流临界值的一个上下界估计。     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

Optimal Equilibria in the Non-Cooperative Game Associated with Cost Spanning Tree Problems

We study the Pareto optimal equilibria payoffs of the non-cooperative game associated with the cost spanning tree problem. We give two characterisations of these payoffs: one based on the tree they induce and another based on the strategies played by agents. Moreover, an algorithm for computing all these payoffs is provided.