Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

交换网络中广播风暴的产生和生成树协议（STP）对其有效阻止

在交换网络环境中,物理环路可以提高网络的冗余,但容易产生双向的广播环,甚至形成广播风暴,使交换机瘫痪;通过生成树协议生成根网桥,根端口,指定端口和阻塞端口,在逻辑上断开该网段,形成一个无环网络,使网络中无法产生广播环和广播风暴;当其它链路出现故障时,阻塞的端口自动恢复,逻辑断开的线路又被连通,继续传输数据。     

Log-polar height maps for multiple range image registration

We propose a method for coarse registration of multiple range images that uses a log-polar height map (LPHM) as the key for establishing correspondence. The LPHM is a local height map orthogonally mapped on the tangent plane with the log-polar coordinate system. The input range images are roughly represented by signed distance field (SDF) samples. For each SDF sample, an LPHM is generated and is converted to an invariant feature vector. Point correspondence is established by a nearest neighbor search in feature space. The RANSAC algorithm is applied on the corresponding point pairs between each pair of range images, and the pairwise registration of input range images is determined by the extracted inlier point pairs. Finally, the global registration is determined by constructing a view tree, which is the spanning tree that maximizes the total number of inlier point pairs. The result of coarse registration is used as the initial state of the fine registration and modeling. The proposed method was tested on multiple real range image datasets.     

多目标随机运输路径选择的频域优化模型

根据运输系统的随机特性,讨论时间、损耗和流量等优化目标之间的函数关系,采用概率论方法提出一种用于搜索时变、随机运输网络中多目标路径优化的频域生成图模型(FSG),设计相应的优化算法。FSG通过时频域间概率函数的相互转化,可定量分析O-D对之间多目标路径选择概率的动态变化过程,处理连续概率分布和离散经验分布。结合Matlab给出的算例验证了该算法的可行性和有效性。     

Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm

In this paper, we consider the fixed-charge transportation problem (FCTP) in which a fixed cost, sometimes called a setup cost, is incurred if another related variable assumes a nonzero value. To tackle such an NP-hard problem, there are several genetic algorithms based on spanning tree and Prüfer number representation. Contrary to the findings in previous works, considering the genetic algorithm (GA) based on spanning tree, we present a pioneer method to design a chromosome that does not need a repairing procedure for feasibility, i.e. all the produced chromosomes are feasible. Also, we correct the procedure provided in previous works, which designs transportation tree with feasible chromosomes. We show the previous procedure does not produce any transportation tree in some situations. Besides, some new crossover and mutation operators are developed and used in this work. Due to the significant role of crossover and mutation operators on the algorithm’s quality, the operators and parameters need to be accurately calibrated to ensure the best performance. For this purpose, various problem sizes are generated at random and then a robust calibration is applied to the parameters using the Taguchi method. In addition, two problems with different sizes are solved to evaluate the performance of the presented algorithm and to compare that performance with LINGO and also with the solution presented in previous work.     

二层以太网中最优组播树的构建方法

针对二层以太网难以构建最优组播树且收敛速度慢的问题,提出一种新的最优组播树构建方法。该方法将IS-IS协议用于二层以太网络最短路径树的计算,通过扩展链路状态包的CLV改进其通告机制,以便构建最优组播树,且网络拓扑发生变化时可快速重构此最优组播树。测试结果表明,该方法可将组播树的收敛时间从现有方法的10 s~20 s缩短到50 ms,并能确保该组播树为最优组播树。     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

求解最小生成树的一种小生境遗传禁忌算法

针对最小生成树问题,提出了一种小生境遗传禁忌算法。算法中使用Prfer数对生成树进行编码。在选择交叉之前使用小生境技术,使得被选中交叉的个体之间的适应值的距离大于一定的阈值,从而保证了个体的多样性。遗传变异算子使用禁忌搜索算法,提高了遗传算法的局部搜索能力,加快了算法的收敛速度。模拟实验结果证明该算法是有效的。     

A graph-theoretic model for optimizing queries involving methods

Traditional algorithms for optimizing the execution order of joins are no more valid when selections and projections involve methods and become very expensive operations. Selections and projections could be even more costly than joins such that they are pulled above joins, rather than pushed down in a query tree. In this paper, we take a fundamental look at how to approach query optimization from a top-down design perspective, rather than trying to force one model to fit into another. We present a graph model which is designed to characterize execution plans. Each edge and each vertex of the graph is assigned a weight to model execution plans. We also design algorithms that use these weights to optimize the execution order of operations. A cost model of these algorithms is developed. Experiments are conducted on the basis of this cost model. The results show that our algorithms are superior to similar work proposed in the literature. Received 20 April 1999 / Accepted 9 August 2000 Published online 20 April 2001     

QoS enhancements for global replication management in peer to peer networks

Replica Management is a key issue to reduce the bandwidth consumption, to improve data availability and to maintain data consistency in large distributed systems. Global Replica Management (GRM) means to maintain the data consistency across the entire network. It is preferable particularly for multi-group distributed systems. On the other hand, GRM is not favorable for many applications because a very large number of message passes is needed for replica management processes. In this paper, in order to reduce the number of message passes needed to achieve the efficient GRM strategy, an interconnection structure called the Distributed Spanning Tree (DST) has been employed. The application of DST converts the peer network into logical layered structures and thereby provides a hierarchical mechanism for replication management. It is proved that this hierarchical approach improves the data availability and consistency across the entire network. In addition to these, it is also proved that the proposed approach reduces the data latency and the required number of message passes for any specific application in the network.