Probability of graphs with large spectral gap by multicanonical Monte Carlo

Graphs with large spectral gap are important in various fields such as biology, sociology and computer science. In designing such graphs, an important question is how the probability of graphs with large spectral gap behaves. A method based on multicanonical Monte Carlo is introduced to quantify the behavior of this probability, which enables us to calculate extreme tails of the distribution. The proposed method is successfully applied to random 3-regular graphs and large deviation probability is estimated.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Strong stability of the mono-tubular heat exchanger equation with output feedback

We investigate asymptotic behavior of the C₀-semigroup T(t) associated with the mono-tubular heat exchanger equation with output feedback by a perturbation method. It is shown that T(t) is bounded if a constraint is satisfied by the parameters and the spatial distribution function. Further, applying the Arendt-Batty-Lyubich-Vu theorem, a criterion is established to judge strong stability of T(t).     

On the implication problem for cardinality constraints and functional dependencies

In database design, integrity constraints are used to express database semantics. They specify the way by that the elements of a database are associated to each other. The implication problem asks whether a given set of constraints entails further constraints. In this paper, we study the finite implication problem for cardinality constraints. Our main result is a complete characterization of closed sets of cardinality constraints. Similar results are obtained for constraint sets containing cardinality constraints, but also key and functional dependencies. Moreover, we construct Armstrong databases for these constraint sets, which are of special interest for example-based deduction in database design.     

Re-engineering of the design process for concurrent engineering

According to the requirements of concurrent engineering, three interdependency relationships (uncoupled relationship, coupled relationship and decoupled relationship) between design activities are presented in this paper. And the coupled relationship plays an important role in concurrent product design process. To represent the precedence relationships among design activities, a directed graph is used to describe the design process. And the interdependency relationship between activities is illustrated by a Design Structure Matrix which is the transpose of the accessibility matrix of the corresponding graph. Using the DSM, an algorithm of recognizing the coupled activities during the design process is presented. Moreover, an algorithm to figure out the order levels of activities during the design process is proposed. And both algorithms are illustrated with a die design example.     

The model-based human body motion analysis system

In this paper, we propose a model-based method to analyze the human walking motion. This system consists of three phases: the preprocessing phase, the model construction phase, and the motion analysis phase. In the experimental results, we show that our system not only analyzes the motion characteristics of the human body, but also recognizes the motion type of the input image sequences. Finally, the synthesized motion sequences are illustrated for verification. The major contributions of this research are: (1) developing a skeleton-based method to analyze the human motion; (2) using Hidden Markov Model (HMM) and posture patterns to describe the motion type.     

A new neural network algorithm for planarization problems

To deal with the planarization problem widely used in many applications including routing very-large-scale integration （VLSI） circuits, this paper points out that only when its vertices are arranged in some specific order in a line can a planar graph be embedded on a line without any cross connections or cross edges. Energy function is proposed to meet the need of embedding a graph on a single line and route it correctly. A Hopfield network is designed according to the proposed energy function for such embedding and routing. The advantage of the proposed method is that it not only can detect if a graph is a planar one or not, but also can embed a planar graph or the maximal planar subgraph of a non-planar graph on a single line. In addition, simulated annealing is employed for helping the network to escape from local minima during the running of the Hopfield network. Experiments of the proposed method and its comparison with some existent conventional methods were performed and the results indicate that the proposed method is of great feasibility and effectiveness especially for the planarization problem of large graphs.     

Robust stability and H-infinity control for uncertain discrete-time Markovian jump singular systems

The robust stability and stabilization, and H-infinity control problems for discrete-time Markovian jump singular systems with parameter uncertainties are discussed. Based on the restricted system equivalent （r.s.e.） transformation and by introducing new state vectors, the singular system is transformed into a discrete-time Markovian jump standard linear system, and the linear matrix inequality （LMI） conditions for the discrete-time Markovian jump singular systems to be regular, causal, stochastically stable, and stochastically stable with 7- disturbance attenuation are obtained, respectively. With these conditions, the robust state feedback stochastic stabilization problem and H-infinity control problem are solved, and the LMI conditions are obtained. A numerical example illustrates the effectiveness of the method given in the oaoer.     

扩展时间事件图的能达性与能控序列

利用图论方法在双子结构中研究扩展时间事件图的某些问题,获得了能达性的一个充分必要条件和基于能达性的标准结构。在此基础上,把监控理论中的能控序列的分量分为本质不同的３类,进而得到能控序列的简化求解方法。     

Dynamics of Flexible Multibody Systems Using Virtual Work and Linear Graph Theory

By combining linear graph theory with the principle of virtualwork, a dynamic formulation is obtained that extends graph-theoreticmodelling methods to the analysis of flexible multibody systems. Thesystem is represented by a linear graph, in which nodes representreference frames on rigid and flexible bodies, and edges representcomponents that connect these frames. By selecting a spanning tree forthe graph, the analyst can choose the set of coordinates appearing inthe final system of equations. This set can include absolute, joint, orelastic coordinates, or some combination thereof. If desired, allnon-working constraint forces and torques can be automaticallyeliminated from the dynamic equations by exploiting the properties ofvirtual work. The formulation has been implemented in a computerprogram, DynaFlex, that generates the equations of motion in symbolicform. Three examples are presented to demonstrate the application of theformulation, and to validate the symbolic computer implementation.