单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

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

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

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

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

一类特殊矩阵的逆特征值问题

本文主要讨论如下形式矩阵的逆特征值问题:即对给定n个实数λ_1>λ_2>…>λ_2与n-1个实数μ_1>μ_2>…>μ_(n-1),满足λ_1>μ_1>λ_2>…>λ_(n-1)>μ_(n-1)>λ_n,在α_2>α_3>…>α_(n-1)的条件下,存在唯一的一个矩阵A_n是以λ_i为其特征值;且其截边矩阵的特征值为μ_1,μ_2,…,μ_(n-1).     

对称的运输问题及其逆问题

本文对［１,２,６］中提出的运输问题进行了推广,并提出了一个强多项式算法,从而改进了原有的结果．同时对对称的运输问题的逆问题进行了研究,并借助于最小费用循环流技术得到了一个强多项式算法．     

一类三维逆时热传导问题的数值求解

该文考虑一类三维逆时热传导问题的数值解法.基于有限差分时间离散,并结合伽辽金(Galerkin)方法对空间进行有限元离散,导出刚度矩阵及载荷向量,对热传导问题进行数值求解.针对反问题,利用分离变量法建立T时刻温度场与初始温度场之间的对应关系,给出了反演公式,并在一定先验假设条件下证明了反问题的局部稳定性.为克服反问题求...     

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

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

求解一类非光滑优化问题的改进变尺度方法

1 引言 近来，人们对用过剩其函数来表示信号的处理方法表现出极大的兴趣，原因是基函数类越大所表示出的函数类就越大，人们通常采用小波基和Gabor基，本文的目的是构造一个寻找优化（或最优）基函数的算法，该算法的出发点是从过剩的其函数中选择紧支撑的基向量。     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

Constrained Inverse Minimum Spanning Tree Problems under the Bottleneck-Type Hamming Distance

In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the weights of edges can be modified only within given intervals. We further consider the constrained case in which the total modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover problems. This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02).     

Minimum Spanning Trees with Sums of Ratios

We present an algorithm for finding a minimum spanning tree where the costs are the sum of two linear ratios. We show how upper and lower bounds may be quickly generated. By associating each ratio value with a new variable in `image space,' we show how to tighten these bounds by optimally solving a sequence of constrained minimum spanning tree problems. The resulting iterative algorithm then finds the globally optimal solution. Two procedures are presented to speed up the basic algorithm. One relies on the structure of the problem to find a locally optimal solution while the other is independent of the problem structure. Both are shown to be effective in reducing the computational effort. Numerical results are presented.     

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.     

On the Minimum Spanning Tree Determined by n Points in the Unit Square

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＡｍｉｎｉｍｕｍｓｐａｎｎｉｎｇｔｒｅｅ（ＭＳＴ）ｉｓｗｉｄｅｌｙａｐｐｌｉｅｄｔｏｔｈｅｆｉｅｌｄｓｏｆｃｏｍｐｕｔｅｒ,ｃｏｍｍｕｎｉｃａｔｉｏｎ,ｎｅｒｗｏｒｋａｎｄｓｏｏｎ．Ｍａｎｙｒｅｓｕｌｔｓｈａｖｅｂｅｅｎｏｂｔａｉｎｅｓ,ｂｕｔｆｅｗｏｆｔｈｅｍｄｅａｌｗｉｔｈｔｈｅｗｏｒｓｔ－ｃａｓｅａｎａｌｙｓｉｓｆｏｒｔｈｅｇｉｖｅｎｆｉｎｉｔｅｒｅｇｉｏｎ．Ｉｎｆａｃｔ,ｉｔｉｓａｍａｘｉｍｉｎｐｒｏｂｌｅｍ（ｓｅｅ［１］——［３］）．Ｔｈｉｓｐａｐｅｒｉ…     

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.     

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.     

The Complexity of Minimum Ratio Spanning Tree Problems

We examine the complexity of two minimum spanning tree problems with rational objective functions. We show that the Minimum Ratio Spanning Tree problem is NP-hard when the denominator is unrestricted in sign, thereby sharpening a previous complexity result. We then consider an extension of this problem where the objective function is the sum of two linear ratios whose numerators and denominators are strictly positive. This problem is shown to be NP-hard as well. We conclude with some results characterizing sufficient conditions for a globally optimal solution.     

实对称矩阵的一类逆特征值问题

利用矩阵的奇异值分解及广义逆，给出了矩阵约束下矩阵反问题AX=B有实对称解的充分必要条件及其通解的表达式．此外，给出了在矩阵方程的解集合中与给定矩阵的最佳逼近解的表达式．     

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.     

轮图和多轮图的生成树的计数

本文应用计算生成树个数的有向图方法、分块矩阵的行列式计算法以及常系数线性递归方程的解法 ,计算得到轮图和多轮图的生成树个数的表达式 (显式或递推式 )