The objective of critical nodes problem is to minimize pair-wise connectivity as a result of removing a specific number of nodes in the residual graph. From a mathematical modeling perspective, it comes the truth that the more the number of fragmented components and the evenly distributed of disconnected sub-graphs, the better the quality of the solution. Basing on this conclusion, we proposed a new Cluster Expansion Method for Critical Node Problem (CEMCNP), which on the one hand exploits a contraction mechanism to greedy simplify the complexity of sparse graph model, and on the other hand adopts an incremental cluster expansion approach in order to maintain the size of formed component within reasonable limitation. The proposed algorithm also relies heavily on the idea of multi-start iterative local search algorithm, whereas brings in a diversified late acceptance local search strategy to keep the balance between interleaving diversification and intensification in the process of neighborhood search. Extensive evaluations show that CEMCNP running on 35 of total 42 benchmark instances are superior to the outcome of KBV, while holding 3 previous best results out of the challenging instances. In addition, CEMCNP also demonstrates equivalent performance in comparison with the existing MANCNP and VPMS algorithms over 22 of total 42 graph models with fewer number of node exchange operations.

For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.

A data-flow program net is a graph representation of data-flow programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Minimum firing (completion) time T of a program net is an important element in computing parallel degree PARAdeg residing in a data-flow program and is defined as the minimum time when the program net is executed by enough many processors. In this paper, we propose algorithms to efficiently compute T by contracting AND-nodes generally for self-cleaning SWITCH-less program nets with arbitrary node firing time and give the experimental results of the algorithms to show the efficiency.

In this paper, we propose a new lemma facility, called the strong contraction rule, for model elimination calculus, and we study some implementation issues of strong contraction in a PTTP-based theorem prover. Strong contraction has the ability to shorten possible proofs and prevent some irrelevant computation to a target goal. Strong contraction never broadens the search space, in principle, and thus, has a stable effect on the acceleration of top-down proof search. However, it is difficult to embed the strong contraction into a PTTP-based theorem prover, because strong contraction imposes a truncation operation of center chains in model elimination calculus. We show a self-truncation-style Prolog code, which makes it possible to retain the high performance of a PTTP-based prover with strong contraction. Finally, we evaluate the performance and effect of strong contraction by performing some experiments.

Various models of a neuron have been proposed and many studies about them and their networks have been reported. Among these neurons, this paper describes a study about the model of a neuron providing its own feedback input and possesing a chaotic dynamics. Using a return map or a histogram of laminar length, type-I intermittency is recognized in a recurrent neuron and its network. A posibility of controlling dynamics in recurrent neural networks is also mentioned a little in this paper.

It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. In this paper, a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees is presented. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in O(log(n1)log(n2)) time using O(n1n2) processors on a CREW PRAM, where n1 and n2 denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.