Self‐destructive percolation as a limit of forest‐fire models on regular rooted trees

Let T be a regular rooted tree. For every natural number n, let T_n be the finite subtree of vertices with graph distance at most n from the root. Consider the following forest‐fire model on T_n: Each vertex can be “vacant” or “occupied”. At time 0 all vertices are vacant. Then the process is governed by two opposing mechanisms: Vertices become occupied at rate 1, independently for all vertices. Independently thereof and independently for all vertices, “lightning” hits vertices at rate λ(n) > 0. When a vertex is hit by lightning, its occupied cluster becomes vacant instantaneously. Now suppose that λ(n) decays exponentially in n but much more slowly than 1/|T_n|, where |T_n| denotes the number of vertices of T_n. We show that then there exist such that between time 0 and time the forest‐fire model on T_n tends to the following process on T as n goes to infinity: At time 0 all vertices are vacant. Between time 0 and time τ vertices become occupied at rate 1, independently for all vertices. Immediately before time τ there are infinitely many infinite occupied clusters. At time τ all these clusters become vacant. Between time τ and time vertices again become occupied at rate 1, independently for all vertices. At time all occupied clusters are finite. This process is a dynamic version of self‐destructive percolation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 86–113, 2017     

Central limit theorems for the radial spanning tree

Consider a homogeneous Poisson point process in a compact convex set in d‐dimensional Euclidean space which has interior points and contains the origin. The radial spanning tree is constructed by connecting each point of the Poisson point process with its nearest neighbour that is closer to the origin. For increasing intensity of the underlying Poisson point process the paper provides expectation and variance asymptotics as well as central limit theorems with rates of convergence for a class of edge functionals including the total edge length. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 262–286, 2017     

Parallel lightweight wavelet tree,suffix array and FM-index construction

We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.     

“分路”方法在树系统动力学分析中的应用

本文把单开链形式的Ｌ－Ｅ法和Ｎ－Ｅ法动力学方程推广到树形系统，引进了“虚体”、“虚路”等概念，在此基础提出了“分路”思想，这种方法具有建模效率高，分析难度低，适合于计算机编程等优点，是一种处理树系统动力学的好方法。     

Protected Branches in Ordered Trees

In this paper, we consider the class of ordered trees and its two subclasses, bushes and planted trees, which consist of the ordered trees with root degree at least $2$ and with root degree $1$ respectively. In these three classes, we study the number of trees of size $n$ with $k$ protected (resp. unprotected) branches, and the total number of branches (resp. protected branches, unprotected branches) among all trees of size $n$. The explicit formulas as well as the generating functions are obtained. Furthermore, we find that, in each class, as $n$ goes to infinity, the proportion of protected branches among all branches in all trees of size $n$ approaches $ 1/3$.     

Theoretical analysis of excited states and energy transfer mechanism in conjugated dendrimers

The excited states of the phenylene ethynylene dendrimer are investigated comprehensively by various electronic‐structure methods. Several computational methods, including SCS‐ADC(2), TDHF, TDDFT with different functionals (B3LYP, BH&HLYP, CAM‐B3LYP), and DFT/MRCI, are applied in systematic calculations. The theoretical approach based on the one‐electron transition density matrix is used to understand the electronic characters of excited states, particularly the contributions of local excitations and charge‐transfer excitations within all interacting conjugated branches. Furthermore, the potential energy curves of low‐lying electronic states as the functions of ethynylene bonds are constructed at different theoretical levels. This work provides us theoretical insights on the intramolecular excited‐state energy transfer mechanism of the dendrimers at the state‐of‐the‐art electronic‐structure theories. © 2014 Wiley Periodicals, Inc.     

大型结构静强度可靠性分析程序及其应用

本文全面介绍了大型结构静强度可靠性分析程序的原理、功能特点及应用实例。     

The Game Saturation Number of a Graph

Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P₄‐saturation game on .     

三元区间数型多属性决策正交投影模型及其在边坡支护方案评价中的应用

针对用TOPSIS法进行三元区间数型多属性决策的不足,用各方案到"理想方案"的"垂面"距离代替TOPSIS法中的欧氏距离,提出一种三元区间数型多属性决策正交投影模型.模型将"理想方案"平移至坐标原点后,转换为0向量,只用平移后的"负理想方案"计算各方案到"理想方案"的"垂面"距离,根据距离最小原则排序得到最终决策结果.通过一个边坡支护方案评价的例子进行了计算分析,并与用其他方法得到的结果进行了对比,说明了模型的有效性.     

Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O ^*(3 ^k ), where k is the number of terminal nodes to be connected. We improve its running time to O ^*(2.684 ^k ) by showing that the optimum Steiner tree T can be partitioned into T = T ₁∪ T ₂ ∪ T ₃ in a certain way such that each T _i is a minimum Steiner tree in a suitable contracted graph G _i with less than terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O ^*(2.386 ^k ). In this case, our splitting technique yields an improvement to O ^*(2.335 ^k ).