图形转换的一种方法

大量工业和工程系统的设计通常都可通过使用各种形式的流程图来进行。例如生产处理和数据处理。ＧＴＥＳ是应用人工智能技术开发的支持结构数据设计和信息处理的专家系统。本系统使用数据流图定义软硬件结构,其中结点表示数据处理步骤,有向弧表示处理步骤之间的数据流。由用户自定义总的处理图开始本专家系统通过应用转换规则来转换这一图形,以使该处理图能满足已说明的设计目标和硬件条件。虽然本专家系统的特殊应用领域为数据和     

Drawings of graphs on surfaces with few crossings

We give drawings of a complete graphK _n withO(n ⁴ log² g/g) many crossings on an orientable or nonorientable surface of genusg 2. We use these drawings ofK _n and give a polynomial-time algorithm for drawing any graph withn vertices andm edges withO(m ² log² g/g) many crossings on an orientable or nonorientable surface of genusg 2. Moreover, we derive lower bounds on the crossing number of any graph on a surface of genusg 0. The number of crossings in the drawings produced by our algorithm are within a multiplicative factor ofO(log² g) from the lower bound (and hence from the optimal) for any graph withm 8n andn ²/m g m/64.The research of the third and the fourth authors was partially supported by Grant No. 2/1138/94 of the Slovak Academy of Sciences and by EC Cooperative action IC1000 Algorithms for Future Technologies (Project ALTEC). A preliminary version of this paper was presented at WG93 and published in Lecture Notes in Computer Science, Vol. 790, 1993, pp. 388–396.     

Simulating BPP using a general weak random source

We show how to simulate BPP and approximation algorithms in polynomial time using the output from a -source. A -source is a weak random source that is asked only once forR bits, and must output anR-bit string according to some distribution that places probability no more than 2^–R on any particular string. We also give an application to the unapproximability of MAX CLIQUE.This paper appeared in preliminary form in theProceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 79–89. Most of this research was done while the author was at U.C. Berkeley, and supported by an AT&T Graduate Fellowship, NSF PYI Grant No. CCR-8896202, and NSF Grant No. IRI-8902813. Part of this research was done while the author was at MIT, supported by an NSF Postdoctoral Fellowship, NSF Grant No. 92-12184 CCR, and DARPA Grant No. N00014-92-J-1799. Part of this research was done at UT Austin, where the author was supported by NSF NYI Grant No. CCR-9457799.     

基于PERT图的虚拟拆装过程建模

提出了使用PERT图来建立虚拟拆装过程模型的方法,根据零件之间的约束关系构造PERT图及其对应的依赖矩阵,并且能够根据它来指导虚拟拆装训练过程的实施.所提供的方法在对某设备的虚拟维修中得到了验证.     

二进制翻译中代码生成的子图覆盖算法

二进制翻译技术能够有效解决二进制兼容问题,促进新型体系结构的发展,也是虚拟机技术的重要组成部分,具有重要的研究和应用价值,但是其效率仍然有待提升,特别是目标代码生成的效率。设计了一种高效的目标代码生成算法——代码生成的子图覆盖算法(subgraph covering for code generation,SCCG),能够以尽可能少的代价生成精简的目标代码。该算法应用数据流图对二进制代码中的基本块进行建模,获取指令间的数据相关,并采用基于子图覆盖的贪心算法得到目标代码。在TransARM原型系统中进行了实现和测试,结果表明该算法获得了更优质的目标代码,并且成本得到了有效控制。     

Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control

The spectral properties of the incidence matrix of the communication graph are exploited to provide solutions to two multi-agent control problems. In particular, we consider the problem of state agreement with quantized communication and the problem of distance-based formation control. In both cases, stabilizing control laws are provided when the communication graph is a tree. It is shown how the relation between tree graphs and the null space of the corresponding incidence matrix encode fundamental properties for these two multi-agent control problems.     

Forced consensus in networks of double integrator systems with delayed input

This communique presents forced second-order consensus protocols with communication time-delays for the network of agents with double integrator dynamics and gives a measure of the robustness of the protocols to the communication time-delays. By employing a frequency domain method, it is proven that the forced consensus is achieved asymptotically for appropriate time-delay if the network is connected. Particularly, the maximum fixed time-delay that can be tolerated by the network is found. The forced consensus protocols are distributed in the sense that each agent only needs information from its neighboring agents, which reduces the complexity of connections between agents significantly. Numerical simulation results are provided to demonstrate the effectiveness and the sharpness of the theoretical results.     

Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

Two algorithms for minimum 2-connected r-hop dominating set

For a graph G=(V,E), a subset D⊆V is an r-hop dominating set if every vertex u∈V−D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of G induced by D is 2-connected. In this paper, we present two approximation algorithms to compute minimum 2-connected r-hop dominating set. The first one is a greedy algorithm using ear decomposition of 2-connected graphs. This algorithm is applicable to any 2-connected general graph. The second one is a three-phase algorithm which is only applicable to unit disk graphs. For both algorithms, performance ratios are given.     

Combination framework of rendezvous algorithm for multi‐agent systems with limited sensing ranges

In this paper, we present a novel rendezvous algorithm framework ‐ the combination framework, which is named after the term convex combination in computational geometry. The convergence of the proposed algorithms is proved based on the novel tools from the recent results in graph theory and consensus study. It has been observed that the circumcenter algorithm can be considered as a special case of the combination framework. Moreover, the relevant analysis provides us a novel viewpoint on designing and the rendezvous rate of rendezvous algorithms for networked multi‐agent systems with limited sensing ranges. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society