直径为4的整树新类

整图是指图的邻接矩阵的特征值全为整数的图。研究了直径为4的整树。通过求某些特定的丢番图方程,构造了具有无穷多个这样的整树新类。     

高精度圆柱直径大量程在线测量系统

高精度圆柱体是机械制造及各种高精度装备的核心器件,由于需求量大,其在线高精度检测是生产质量控制的关键环节.本文针对圆柱体直径高精度测量技术展开研究.设计V型测量平台,增大测量系统的量程,适应各种类型圆柱体测量.采用光学显微镜头、CCD摄像机和LED背景光源组件视觉系统,基于视觉检测技术实现高精度测量.实验数据显示,系统的重复测量精度在0.4 μm之内,绝对测量精度在3 μm之内,符合大部分高精度圆柱体的检测要求.     

Scheduling trees with large communication delays on two identical processors

We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical integer communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomial-time algorithm for complete binary trees.This work has been partially supported by the French-Greek bilateral exchange program PLATON and the GDR-PRS Ordonnancement pour le parallélisme program of the French government.     

Partitioning trees: Matching,domination, and maximum diameter

A matching and a dominating set in a graph G are related in that they determine diameter-bounded subtree partitions of G. For a maximum matching and a minimum dominating set, the associate partitions have the fewest numbers of trees. The problem of determining a minimum dominating set in an arbitrary graph G is known to be NP-complete. In this paper we present a linear algorithm for partitioning an arbitrary tree into a minimum number of subtrees, each having a diameter at mostk, for a givenk.Research supported in part by the National Science Foundation under Grant ENG 7902960.Research supported in part by the National Science Foundation under Grant STI 7902960.     

Constructing large suffix trees on a computational grid

The suffix tree is a key data structure for biological sequence analysis, since it permits efficient solutions to many string-based problems. Constructing large suffix trees is challenging because of high memory overheads and poor memory locality. Even though efficient suffix tree construction algorithms exist, their run-time is still very high for long DNA sequences such as whole human chromosomes. In this paper, we are using a hierarchical grid system as a computational platform in order to reduce this run-time significantly. To achieve an efficient mapping onto this type of architecture we introduce a parallel suffix tree construction algorithm that makes use of a new data structure called the common prefix suffix tree. Using this algorithm together with a dynamic load balancing strategy we show that our distributed grid implementation leads to significant run-time savings.     

On-line construction of parameterized suffix trees for large alphabets

We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomized O(n) time, where n is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem.     

Nearly exact mining of frequent trees in large networks

Mining frequent patterns in a single network (graph) poses a number of challenges. Already only to match one path pattern to a network under subgraph isomorphism is NP-complete. Classical matching algorithms become intractable even for reasonably small patterns, on networks which are large or have a high average degree. Based on recent advances in parameterized complexity theory, we propose a novel miner for rooted trees in networks. The miner, for a fixed parameter $k$ k (maximal pattern size), can mine all rooted trees with delay linear in the size of the network and only mildly exponential in the fixed parameter $k$ k . This allows us to mine tractably, rooted trees, in large networks such as the WWW or social networks. We establish the practical applicability of our miner, by presenting an experimental evaluation on both synthetic and real-world data.     

Key establishment in large dynamic groups using one-way function trees

We present, implement, and analyze a new scalable centralized algorithm, called OFT, for establishing shared cryptographic keys in large, dynamically changing groups. Our algorithm is based on a novel application of one-way function trees. In comparison with the top-down logical key hierarchy (LKH) method of Wallner et al., our bottom-up algorithm approximately halves the number of bits that need to be broadcast to members in order to rekey after a member is added or evicted. The number of keys stored by group members, the number of keys broadcast to the group when new members are added or evicted, and the computational efforts of group members, are logarithmic in the number of group members. Among the hierarchical methods, OFT is the first to achieve an approximate halving in broadcast length, an idea on which subsequent algorithms have built. Our algorithm provides complete forward and backward security: Newly admitted group members cannot read previous messages, and evicted members cannot read future messages, even with collusion by arbitrarily many evicted members. In addition, and unlike LKH, our algorithm has the option of being member contributory in that members can be allowed to contribute entropy to the group key. Running on a Pentium II, our prototype has handled groups with up to 10 million members. This algorithm offers a new scalable method for establishing group session keys for secure large-group applications such as broadcast encryption, electronic conferences, multicast sessions, and military command and control.     

沉入式大直径圆筒结构倾覆转动点数值分析

针对各种关于沉入式大直径圆筒结构稳定性计算方法的基本假设、分析思路、参数取值和计算结果等存在较大差异的情况,通过ABAQUS模拟其在竖向载荷和水平载荷作用下的倾覆. 该方法由位移变化寻找其倾覆转动点,分析其倾覆转动点随参数变化的规律.数值模拟结果与解析计算结果虽然存在约±20%的误差,但是数值解与解析解关于转动点位移随圆筒各参数变化的规律表现一致,有助于沉入式大直径圆筒结构的倾覆稳定性分析.     

Decomposing the Laplacian

A correction is made and an elementary derivation is given of Clark's (ibid., vol.11, p.43-57, 1989) decomposition of the Laplacian Δ²f(x,y) into a second directional derivative in the gradient direction of f, and a product of gradient magnitude by curvature of the level curve through f(x,y)     

Self‐adjusting trees in practice for large text collections

Splay and randomized search trees (RSTs) are self‐balancing binary tree structures with little or no space overhead compared to a standard binary search tree (BST). Both trees are intended for use in applications where node accesses are skewed, for example in gathering the distinct words in a large text collection for index construction. We investigate the efficiency of these trees for such vocabulary accumulation. Surprisingly, unmodified splaying and RSTs are on average around 25% slower than using a standard binary tree. We investigate heuristics to limit splay tree reorganization costs and show their effectiveness in practice. In particular, a periodic rotation scheme improves the speed of splaying by 27%, while other proposed heuristics are less effective. We also report the performance of efficient bit‐wise hashing and red–blacktrees for comparison. Copyright © 2001 John Wiley & Sons, Ltd.     

任意多面体的环链剖分算法

文章提出了一种对任意多面体不添加顶点的凸剖分方法,它对多面体的剖分个数接近最少。方法是从多面体的棱和对角棱所构成的所有环链中按形成剖分面最少和周长最短的要求选取一个最好的环,利用这个环的各个边所形成的一系列面对多面体进行一次剖分。这种方法可找到对多面体不添加顶点剖分的最好剖分面,使剖分的次数接近最少,同时此方法可对任意多面体进行剖分。     

Decomposing Simulation Results with Respect to Exogenous Shocks

When a general equilibrium model is solved, there areoften a large number of exogenous shocks. The changein each endogenous variable obviously depends on thesedifferent shocks.We point out a natural way of decomposing thechanges (or percentage changes) in the endogenousvariables as sums of the contributions made by thechange in each exogenous variable. The change in anyendogenous variable is exactly equal to the sum of thecontributions to this change attributed to each of theexogenous variables.The contribution of a group of exogenous variablesto the change (or percentage change) in any endogenousvariable is defined to be the sum of the contributionsof the individual exogenous variables in the group. Ifall the exogenous variables are partitioned intoseveral groups that are mutually exclusive andexhaustive, the change (or percentage change) in anyendogenous variable is just the sum of thecontributions made by these groups.We introduce, and motivate, these decompositions inthe context of a published GTAP application in which10 regions remove import tariffs and non-tariffbarriers to imports. We use the methods given in thispaper to report numerical values for the contributionsto the welfare gains of various regions due to tariffreductions by particular regions or groups of regionsin this simulation. We show how the values obtainedvia the decomposition are related to the estimates inthe published study of the contributions to welfaregain due to certain groups of tariff reductions.We describe a practical procedure for calculatingthe contributions of individual exogenous variables orgroups of exogenous variables to the changes (or thepercentage changes) in all of the endogenousvariables. This procedure, which applies to a widerange of general equilibrium models, is now automatedin GEMPACK in a version that will be made publiclyavailable in the future.The contributions that make up the decompositionare defined as integrals. As such, they depend on thepath by which the exogenous values move from theirpre-simulation to post-simulation values. We proposeone natural path, namely a straight line between thesetwo points. Along this path, the ordinary rate ofchange is constant for each variable.     

Stepwise design of non-covalent wrapping of large diameter carbon nanotubes by peptides

Single-walled carbon nanotube (SWCNT) is one of the most popular low-dimensional carbon materials in material science, nanomedicine, and nanoscale electronics. Yet the application of the SWCNTs was hindered by the self-aggregation. To purify and disperse the SWCNTs, non-covalent wrapping is one of the effective options to overcome such defects. In this work, two kinds of short peptides were designed to facilitate the modification of large-diameter SWCNT. The design of the peptide was carried out in a stepwise manner. The effective residues of helix-rich and sheet-rich proteins on SWCNT were studied at the first step, and then a coarse model peptide composed of the key adsorption residues above was built to investigate the adsorption dynamics on SWCNT. In the end, the residues include long alkyl side chain and that include aromatic rings were found to play key roles on the adsorption of protein/peptide on hydrophobic SWCNT. And two peptides rich in the long alkyl chain and aromatic rings were constructed respectively. The predominant adsorption capabilities of the two kinds of peptides were discerned by the adsorption details.     

Decomposing heterogeneous inter-entity relationship updates

New problems of updating views involving inter-entity relationships or joins are identified, beyond those reported previously in the literature. A general purpose method and a set of algorithms are presented for correctly decomposing multilingual update requests on a network of distributed heterogeneous databases. The method and algorithm also apply to both homogeneous nondistributed and distributed database environments. The method, called prototype views and update rules, applies to individual relationships in an entity relationship (ER) view of the network database and gives a floorplan for update decomposition. The network database view represents a unified conceptual view of all the individual databases in the heterogeneous network (i.e. of the objects shared across the network). The update request is decomposed into a sequence of intermediate control language steps to subsequently guide the particular updates to each of the underlying databases in the network. Individual database updates are performed by each particular database management system (DBMS)     

Approximation algorithms for the bandwidth minimization problem for a large class of trees

We present approximation algorithms for the bandwidth minimization problem (BMP) for a large class of trees. The BMP is NP-hard, even for trees of maximum node degree 3. The problem finds applications in many areas, including VLSI layout, multiprocessor scheduling, and matrix processing, and has been studied for both graphs and matrices. We study the problem on trees having the following property: given any tree nodev, the depth difference of any two nonempty subtrees rooted atv is bounded by a constantk. We call such treesh(k)trees orgeneralized height-balanced (GHB)trees. The above definition extends the class of balanced trees to trees with depthd=Θ(\N\). For any tree in the above defined class, anO (logd) times optimal algorithm is presented. Furthermore, we extend the application of the algorithm to trees that simulate theh(k) property, which we callh(k)-like trees, and also provide intuitive ideas for an approximation algorithm for general trees.     

Approximation algorithms for the bandwidth minimization problem for a large class of trees

We present approximation algorithms for the bandwidth minimization problem (BMP) for a large class of trees. The BMP is NP-hard, even for trees of maximum node degree 3. The problem finds applications in many areas, including VLSI layout, multiprocessor scheduling, and matrix processing, and has been studied for both graphs and matrices. We study the problem on trees having the following property: given any tree nodev, the depth difference of any two nonempty subtrees rooted atv is bounded by a constantk. We call such treesh(k)trees orgeneralized height-balanced (GHB)trees. The above definition extends the class of balanced trees to trees with depthd=Θ(\N\). For any tree in the above defined class, anO (logd) times optimal algorithm is presented. Furthermore, we extend the application of the algorithm to trees that simulate theh(k) property, which we callh(k)-like trees, and also provide intuitive ideas for an approximation algorithm for general trees. This work has been supported in part by the Computer Learning Research (CLEAR) Center at the University of Texas at Dallas.