Augmenting Trees to Meet Biconnectivity and Diameter Constraints

Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2. Received April 19, 1999; revised June 5, 2001.     

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,并能确保该组播树为最优组播树。     

基于ADL小波变换的图像压缩算法

提出一种基于自适应方向提升(ADL)小波变换的图像压缩算法。根据灰度共生矩阵角二阶矩的差异,将图像分割成平坦性不同的分块。对纹理信息较少的块,采用一般提升小波变换以减少变换时间。对纹理信息较多的块,采用方向提升小波以提高变换效果。结合多级树集合分裂编码和算术编码对变换系数和方向信息分别进行编码。实验结果表明,与ADL算法相比,该算法能有效减少方向小波变换时间。     

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.