膨胀运算的Minkowski函数表达式的证明和它的一个推广

在形态学中,Minkowski函数完全刻画了Rn中的凸集X的几何特性.但是在实际应用中,往往需要考虑X的形态变换,如膨胀、腐蚀、形态开、形态闭等的形态特性.利用平行凸集中膨胀运算概念给出形态学中膨胀运算的定义,从而引出Minkowski函数表达式,并给予严格的数学证明,在此基础上得到并证明了腐蚀运算的Minkowski函数的表达式.     

Approximations for a Bottleneck Steiner Tree Problem

Abstract. In the design of wireless communication networks, due to a budget limit, suppose we could put totally n+k stations in the plane. However, n of them must be located at given points. Of course, one would like to have the distance between stations as small as possible. The problem is how to choose locations for other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP \neq P , no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than \sqrt 2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane.     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要.本文提出了加权的基于多播节点的多播路由算法（WDDMC算法）.由于改变了DDMC（Destination-Driven routing for low-cost Multicast ）算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树.在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法.该算法的复杂度与DDMC算法完全相同.     

A note on boundingk-terminal reliability

A generalization of a theorem of Lomonosov and Polesskii is proved, which provides a novel method for determining upper bounds on the probability that a graph contains a Steiner tree (k-terminal reliability).This research was supported by NSERC Canada under Grant No. A0579.     

RBF神经网络理论及其在控制中的应用

对ＲＢＦ神经网络的结构、分类、函数逼近理论及训练方法进行了综述，并且对ＲＢＦ网络的优点及问题作了分析，同时介绍了目前ＲＢＦ网络在控制方面应用情况，最后提出了ＲＢＦ网络在控制中的研究及应用新方向。     

VLSI版图设计中的一种优化总体布线方法

本文针对国际上已有的多种BBL总体布线方法进行了研究,提出了一种更有效的基于多子图定向合并生成的布线算法,并在国家重点工程“熊猫系统中实现.实验结果比较表明:我们的总体布线优化技术优于已有的BBL总体布线工具.     

Equispreading tree in Manhattan distance

The equispreading tree on the plane with Manhattan distance, which is a Steiner tree such that all paths from the root to all leaves have the same length, is analyzed. This problem is not only fundamental in computational geometry but also critical for equidistant routings in VLSI clock design. Several characteristics for the trees are discussed together with an algorithm constructing equispreading trees in the bottom-up fashion. This algorithm achieves linear time and space complexity with respect to the number of leaves, and minimizes the path length from the root to leaves. Furthermore, this paper shows that the shortest-path-length equispreading trees are related to the smallest enclosing circles in Manhattan distance.     

On the location of Steiner points in uniformly-oriented Steiner trees

We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m?1.