Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

Augmenting the aho-corasick pattern matching machine

The Aho-Corasick algorithm is a well-known method of determining the occurrences of one of several given pattern strings in a given text string. We address the question of augmenting the pattern matching machine constructed by this algorithm with a new pattern string, both on-line and off-line. We show that augmenting a machine of N nodes with a new pattern string of length m takes Θ(mN) time on-line and Θ(N) time off-line.     

Understanding design patterns — what is the problem?

Design patterns codify proven solutions to recurring design problems. Their proper use within a development context requires that: (i) we understand them; (ii) we ascertain their applicability or relevance to the design problem at hand; and (iii) we apply them faithfully to the problem at hand. We argue that an explicit representation of the design problem solved by a design pattern is key to supporting the three tasks in an integrated fashion. We propose a model‐driven representation of design patterns consisting of triples < MP, MS, T > where MP is a model of the problem solved by the pattern, MS is a model of the solution proposed by the pattern, and T is a model transformation of an instance of the problem into an instance of the solution. Given an object‐oriented design model, we look for model fragments that match MP (call them instances of MP), and when one is found, we apply the transformation T yielding an instance of MS. Easier said than done. Experimentation with an Eclipse Modeling Framework‐based implementation of our approach applied to a number of open‐source software application's raised fundamental questions about: (i) the nature of design patterns in general, and the ones that lend themselves to our approach, and (ii) our understanding and codification of seemingly simple design patterns. In this paper, we present the principles behind our approach, report on the results of applying the approach to the Gang of Four (GoF) design patterns, and discuss the representability of design problems solved by these patterns. Copyright © 2011 John Wiley & Sons, Ltd.     

An efficient approach for the maintenance of user behaviours

Mining sequential patterns is to discover sequential purchasing behaviours for most of the customers from a large number of customer transactions. The strategy of mining sequential patterns focuses on discovering frequent sequences. A frequent sequence is an ordered list of the itemsets purchased by a sufficient number of customers. The previous approaches for mining sequential patterns need to repeatedly scan the database so that they take a large amount of computation time to find frequent sequences. The customer transactions will grow rapidly in a short time, and some of the customer transactions may be antiquated. Consequently, the frequent sequences may be changed due to the insertion of new customer transactions or the deletion of old customer transactions from the database. It may require rediscovering all the patterns by scanning the entire updated customer transaction database. In this paper, we propose an incremental updating technique to maintain the discovered sequential patterns when transactions are inserted into or deleted from the database. Our approach partitions the database into some segments and scans the database segment by segment. For each segment scan, our approach prunes those sequences that cannot be frequent sequences any more to accelerate the finding process of the frequent sequences. Therefore, the number of database scans can be significantly reduced by our approach. The experimental results show that our algorithms are more efficient than other algorithms for the maintenance of mining sequential patterns.     

PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids

In recent years, grid technology has had such a fast growth that it has been used in many scientific experiments and research centers. A large number of storage elements and computational resources are combined to generate a grid which gives us shared access to extra computing power. In particular, data grid deals with data intensive applications and provides intensive resources across widely distributed communities. Data replication is an efficient way for distributing replicas among the data grids, making it possible to access similar data in different locations of the data grid. Replication reduces data access time and improves the performance of the system. In this paper, we propose a new dynamic data replication algorithm named PDDRA that optimizes the traditional algorithms. Our proposed algorithm is based on an assumption: members in a VO (Virtual Organization) have similar interests in files. Based on this assumption and also file access history, PDDRA predicts future needs of grid sites and pre-fetches a sequence of files to the requester grid site, so the next time that this site needs a file, it will be locally available. This will considerably reduce access latency, response time and bandwidth consumption. PDDRA consists of three phases: storing file access patterns, requesting a file and performing replication and pre-fetching and replacement. The algorithm was tested using a grid simulator, OptorSim developed by European Data Grid projects. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, effective network usage, total number of replications, hit ratio and percentage of storage filled.     

Texture analysis of poly-adenylated mRNA staining following global brain ischemia and reperfusion

Texture analysis provides a means to quantify complex changes in microscope images. We previously showed that cytoplasmic poly-adenylated mRNAs form mRNA granules in post-ischemic neurons and that these granules correlated with protein synthesis inhibition and hence cell death. Here we utilized the texture analysis software MaZda to quantify mRNA granules in photomicrographs of the pyramidal cell layer of rat hippocampal region CA3 around 1 h of reperfusion after 10 min of normothermic global cerebral ischemia. At 1 h reperfusion, we observed variations in the texture of mRNA granules amongst samples that were readily quantified by texture analysis. Individual sample variation was consistent with the interpretation that animal-to-animal variations in mRNA granules reflected the time-course of mRNA granule formation. We also used texture analysis to quantify the effect of cycloheximide, given either before or after brain ischemia, on mRNA granules. If administered before ischemia, cycloheximide inhibited mRNA granule formation, but if administered after ischemia did not prevent mRNA granulation, indicating mRNA granule formation is dependent on dissociation of polysomes. We conclude that texture analysis is an effective means for quantifying the complex morphological changes induced in neurons by brain ischemia and reperfusion.     

Fault prediction and the discriminative powers of connectivity-based object-oriented class cohesion metrics

Context

Several metrics have been proposed to measure the extent to which class members are related. Connectivity-based class cohesion metrics measure the degree of connectivity among the class members.

Objective

We propose a new class cohesion metric that has higher discriminative power than any of the existing cohesion metrics. In addition, we empirically compare the connectivity and non-connectivity-based cohesion metrics.

Method

The proposed class cohesion metric is based on counting the number of possible paths in a graph that represents the connectivity pattern of the class members. We theoretically and empirically validate this path connectivity class cohesion (PCCC) metric. The empirical validation compares seven connectivity-based metrics, including PCCC, and 11 non-connectivity-based metrics in terms of discriminative and fault detection powers. The discriminative-power study explores the probability that a cohesion metric will incorrectly determine classes to be cohesively equal when they have different connectivity patterns. The fault detection study investigates whether connectivity-based metrics, including PCCC, better explain the presence of faults from a statistical standpoint in comparison to other non-connectivity-based cohesion metrics, considered individually or in combination.

Results

The theoretical validation demonstrates that PCCC satisfies the key cohesion properties. The results of the empirical studies indicate that, in contrast to other connectivity-based cohesion metrics, PCCC is much better than any comparable cohesion metric in terms of its discriminative power. In addition, the results also indicate that PCCC measures cohesion aspects that are not captured by other metrics, wherein it is considerably better than other connectivity-based metrics but slightly worse than some other non-connectivity-based cohesion metrics in terms of its ability to predict faulty classes.

Conclusion

PCCC is more useful in practice for the applications in which practitioners need to distinguish between the quality of different classes or the quality of different implementations of the same class.     

Lotka-Volterra捕食系统的反步控制设计

通过反步设计方法,研究了Lotka-Volterra捕食模型的全局稳定化问题,得到了使闭环系统在正平衡点处全局渐近稳定的控制规律,其控制效果通过了数值模拟的验证．