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

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

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

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

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

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

有向图中几类支撑树数目的计算公式

将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

瓶颈型Hamming距离下约束最小支撑树的反问题

本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

基于禁忌搜索算法的枢纽航线网络优化设计研究

首先建立了非严格意义上的无容量限制的多重分派p-枢纽中位问题(NSUMApHMP)的混合整数线性规划模型.然后提出了一种基于禁忌搜索和最短路算法解决NSUMApHMP的新的启发式算法.最后利用基准数据对该算法进行了验证.计算结果表明,该算法具有较强寻优能力和较快的求解效率.     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

Minimum Spanning Table and Optimal Expansion of Competence Set

Each directed graph with asymmetric costs defined over its arcs can be represented by a matrix or table, called an expansion table. We explore first the basic properties of cycles and spanning tables of expansion tables, which correspond to the cycles and spanning trees of the directed graph. Then, we derive an algorithm to find a minimum spanning table which corresponds to a minimum spanning tree in the directed graph. Finally, we discuss how to use the algorithm to find the optimal competence set expansion and also discuss related problems.     

A CAPACITY EXPANSION PROBLEM WITH BUDGET CONSTRAINT AND BOTTLENECK LIMITATION

1 IntroductionIn [2] tl1e authors considered a type of coustrained maximim capacity path problem whichcan be described briefly as: kuowing the costs for expallding one unit of capacity along differentedge8 of a l1etwork aud the availabIe budget, how to iucrease the caparities of the edges so thattlle capasity between any pair of nodes in the lletwork can be raised unifornily to the maximumextent? As the total cost is a summation of the expansion costs on all edges, this problem i8related to mi…     

On the inverse problem of minimum spanning tree with partition constraints

In this paper we first discuss the properties of minimum spanning tree and minimum spanning tree with partition constraints. We then concentrate on the inverse problem of minimum spanning tree with partition constraints in which we need to adjust the weights of the edges in a network as less as possible so that a given spanning tree becomes the minimum one among all spanning trees that satisfy the partition restriction. Based on the calculation of maximum cost flow in networks, we propose a strongly polynomial algorithm for solving the problem.The author gratefully acknowledges the partial support of Croucher Foundation.     

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。     

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

次最小树及其相关问题-算法设计和复杂性分析

支撑树问题已经有很长的研究历史了,见[1].在许多工程问题中,需要产生一个网络G的所有支撑树,见[2,3,4].当G为赋权图时,每棵支撑树T有长度L（T）.在产生G的所有支撑树时,许多工程问题希望按照L（T）的非降顺序产生,见[5,6].在按照L（T）的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大（可以高达nn-2个）,因此算法的计算量非常大.本文希望能够按照L（T）的严格上升顺序产生所有的支撑树,从而避免大量的重复计算.     

最小费用k度限制树对策

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