Efficient exponential-time algorithms for edit distance between unordered trees

The edit distance problem for rooted unordered trees is known to be NP-hard. Based on this fact, this paper studies exponential-time algorithms for the problem. For a general case, an $O(\min ({1.26}^{n_1+n_2},2^{b_1+b_2}\cdot \text{<mi mathvariant="italic" is="true">poly</mi>}(n_1,n_2)))$ time algorithm is presented, where $n_1$ and $n_2$ are the numbers of nodes and $b_1$ and $b_2$ are the numbers of branching nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in $O({(1+ϵ)}^{n_1+n_2})$ time for any fixed $ϵ>0$. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.     

基于虚拟源时间反转的经颅超声精确聚焦*

针对经颅超声难以精确聚焦的问题,本文研究了基于虚拟源的时间反转方法,建立颅骨二维数字模型,在聚焦目标处设置虚拟声源,利用时域有限差分法模拟超声时间反转过程,并考察基于虚拟源时间反转方法的聚焦效果。数值仿真结果表明,基于虚拟源的时间反转方法可以实现经颅超声的精确聚焦,聚焦强度和精度好于传统的相控聚焦;换能器中心频率和数量对聚焦效果的影响规律与相控聚焦时类似;该方法可以同时向多个焦点聚焦,并自适应调节各焦点处声压幅度。     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

Existence of extremal solutions by approximation to a first-order initial dynamic equation with Carathéodory's conditions and discontinuous non-linearities*

This paper is devoted to the study of the existence of extremal solutions to a first-order initial value problem on an interval of an arbitrary time scale. We prove the existence of extremal solutions for problems satisfying Carathéodory's conditions. Moreover, they are approximated uniformly by a sequence of lower and upper solutions to this problem, respectively.

We also can warrant the existence and approximation of extremal solutions for the problem by relaxing their continuity properties.     

Distortion theorem for Bloch mappings on the unit ball <Emphasis Type="Italic">ℬ</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper, we obtain a version of subordination lemma for hyperbolic disk relative to hyperbolic geometry on the unit disk D. This subordination lemma yields the distortion theorem for Bloch mappings f ∈ H（B^n） satisfying ｜｜f｜｜0 = 1 and det f＇（0） = α ∈ （0, 1], where｜｜f｜｜0 = sup{（1 - ｜z｜^2 ）n＋1/2n det（f＇（z））[1/n ： z ∈ B^n}. Here we establish the distortion theorem from a unified perspective and generalize some known results. This distortion theorem enables us to obtain a lower bound for the radius of the largest univalent ball in the image of f centered at f（0）. When a = 1, the lower bound reduces to that of Bloch constant found by Liu. When n = 1, our distortion theorem coincides with that of Bonk, Minda and Yanagihara.     

Initial classification of joint data in EM estimation of latent class joint model

The latent class mixture-of-experts joint model is one of the important methods for jointly modelling longitudinal and recurrent events data when the underlying population is heterogeneous and there are nonnormally distributed outcomes. The maximum likelihood estimates of parameters in latent class joint model are generally obtained by the EM algorithm. The joint distances between subjects and initial classification of subjects under study are essential to finding good starting values of the EM algorithm through formulas. In this article, separate distances and joint distances of longitudinal markers and recurrent events are proposed for classification purposes, and performance of the initial classifications based on the proposed distances and random classification are compared in a simulation study and demonstrated in an example.     

金银三层纳米管局域表面等离激元共振特性研究

相对于单一金属纳米材料,二金属复合纳米材料具有更大的潜在应用价值.基于时域有限差分方法,研究了SiO₂-Ag-Au和SiO₂-Au-Ag二金属三层纳米管的消光光谱,并对其局域表面等离激元共振(Localized Surface Plasmon Resonance,LSPR)特性进行了分析.研究发现,内核尺寸变大将导致上述两种金属纳米管LSPR峰红移;内层金属及外层金属壳层厚度增大均会导致其LSPR峰蓝移.银壳厚度变化对纳米管LSPR的调制作用大于金壳厚度变化造成的影响.上述现象可以利用等离激元杂化理论及自由电子和振荡电子变化的竞争机制进行分析.     

On the subgroup distance problem

We investigate the computational complexity of finding an element of a permutation group H⊆S_n with minimal distance to a given π∈S_n, for different metrics on S_n. We assume that H is given by a set of generators. In particular, the size of H might be exponential in the input size, so that in general the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of S_n, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473-479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l_p distance, Lee’s Distance, Kendall’s tau, and Ulam’s Distance. Moreover, we give an NP-hardness proof for the l_∞ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.     

Evacuation assistants: An extended model for determining effective locations and optimal numbers

The present research presents an extended evacuation field model for simulating crowd emergency evacuation processes under the control of evacuation assistants. Furthermore, a communication field for describing the escape information transmission process and its effect on evacuees is introduced. The effective locations and optimal numbers of evacuation assistants as generated through the model are proposed in an effort to verify as well as enhance existing models. Results show the following. (1) Locating evacuation assistants near exits reduces the time delay for pre-evacuation. (2) There is an optimal number of evacuation assistants for achieving evacuation efficiency; having excessive numbers of evacuation assistants does not improve the evacuation efficiency, and they may result in evacuation time delay and hinder the evacuation efficiency. (3) As the number of evacuees increases, the number of evacuation assistants needed decreases.     

基于Pena距离的加权最小二乘估计的影响分析

利用Pena距离对加权线性最小二乘估计的影响问题进行讨论,得到加权最小二乘估计的Pena距离的表达式,对其性质进行讨论,从而得到高杠异常点的判别方法.文中对Pena距离与Cook距离的性能进行了对比,得到在一定条件下Pena距离优于Cook距离的结论.并通过数值实验对此方法的有效性进行验证.