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.     

Defining syntax-directed translations by tree bimorphisms

We introduce a class of tree bimorphisms that define exactly the translations performed by syntax-directed translation schemata. We also show that these “quasi-alphabetic” tree bimorphisms preserve recognizability, and that their class is closed under composition and inverses.     

Physically Guided Animation of Trees

This paper presents a new method to animate the interaction of a tree with wind both realistically and in real time. The main idea is to combine statistical observations with physical properties in two major parts of tree animation. First, the interaction of a single branch with the forces applied to it is approximated by a novel efficient two step nonlinear deformation method, allowing arbitrary continuous deformations and circumventing the need to segment a branch to model its deformation behavior. Second, the interaction of wind with the dynamic system representing a tree is statistically modeled. By precomputing the response function of branches to turbulent wind in frequency space, the motion of a branch can be synthesized efficiently by sampling a 2D motion texture.
Using a hierarchical form of vertex displacement, both methods can be combined in a single vertex shader, fully leveraging the power of modern GPUs to realistically animate thousands of branches and ten thousands of leaves at practically no cost.     

基于超螺旋模型的头发动态模拟方法

针对现有头发模型缺乏柔性的问题,提出一种改进的基于超螺旋模型的头发建模与仿真方法,将导引发丝构造成具有有限自由度的分段螺旋体,运用拉格朗日力学对发丝运动进行计算。通过改进卷发曲率和捻度的计算方法,并采用自适应控制结构对头发进行重组和细分,提高模拟过程的准确性和稳定性。实验结果证明,该方法可以获得较为逼真的动态模拟头发的效果。     

一种时延受限的最优时延抖动路由算法

研究多播端到端时延受限条件下的最优时延抖动问题,提出一种有效的多播路由算法。通过修改源节点到目的节点的路径,使时延较小的目的节点获得尽可能大的时延值,时延较大的目的节点获得尽可能小的时延值。仿真结果表明,该算法能获得较小的时延抖动。     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

A divide and conquer matheuristic algorithm for the Prize-collecting Steiner Tree Problem

The Prize-collecting Steiner Tree Problem (PCSTP) is a well-known problem in graph theory and combinatorial optimization. It has been successfully applied to solve real problems such as fiber-optic and gas distribution networks design. In this work, we concentrate on its application in biology to perform a functional analysis of genes. It is common to analyze large networks in genomics to infer a hidden knowledge. Due to the NP-hard characteristics of the PCSTP, it is computationally costly, if possible, to achieve exact solutions for such huge instances. Therefore, there is a need for fast and efficient matheuristic algorithms to explore and understand the concealed information in huge biological graphs. In this study, we propose a matheuristic method based on clustering algorithm. The main target of the method is to scale up the applicability of the currently available exact methods to large graph instances, without loosing too much on solution quality. The proposed matheuristic method is composed of a preprocessing procedures, a heuristic clustering algorithm and an exact solver for the PCSTP, applied on sub-graphs. We examine the performance of the proposed method on real-world benchmark instances from biology, and compare its results with those of the exact solver alone, without the heuristic clustering. We obtain solutions in shorter execution time and with negligible optimality gaps. This enables analyzing very large biological networks with the currently available exact solvers.     

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

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

A fuzzy reasoning and fuzzy-analytical hierarchy process based approach to the process of railway risk information: A railway risk management system

Risk management is becoming increasingly important for railway companies in order to safeguard their passengers and employees while improving safety and reducing maintenance costs. However, in many circumstances, the application of probabilistic risk analysis tools may not give satisfactory results because the risk data are incomplete or there is a high level of uncertainty involved in the risk data. This article presents the development of a risk management system for railway risk analysis using fuzzy reasoning approach and fuzzy analytical hierarchy decision making process. In the system, fuzzy reasoning approach (FRA) is employed to estimate the risk level of each hazardous event in terms of failure frequency, consequence severity and consequence probability. This allows imprecision or approximate information in the risk analysis process. Fuzzy analytical hierarchy process (fuzzy-AHP) technique is then incorporated into the risk model to use its advantage in determining the relative importance of the risk contributions so that the risk assessment can be progressed from hazardous event level to hazard group level and finally to railway system level. This risk assessment system can evaluate both qualitative and quantitative risk data and information associated with a railway system effectively and efficiently, which will provide railway risk analysts, managers and engineers with a method and tool to improve their safety management of railway systems and set safety standards. A case study on risk assessment of shunting at Hammersmith depot is used to illustrate the application of the proposed risk assessment system.