In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.

In this paper, we introduce a new decision problem associated with lattices, named the Exact Length Vector Problem (ELVP), and prove the NP-completeness of ELVP in the ∞ norm. Moreover, we define two variants of ELVP. The one is a binary variant of ELVP, named the Binary Exact Length Vector Problem (BELVP), and is shown to be NP-complete in any p norm (1 ≤ p ≤ ∞). The other is a nonnegative variant of ELVP, named the Nonnegative Exact Length Vector Problem (NELVP). NELVP is defined in the 1 norm, and is also shown to be NP-complete.

An improved genetic algorithm for solving the graph planarization problem is presented. The improved genetic algorithm which is designed to embed a graph on a plane, performs crossover and mutation conditionally instead of probability. The improved genetic algorithm is verified by a large number of simulation runs and compared with other algorithms. The experimental results show that the improved genetic algorithm performs remarkably well and outperforms its competitors.

In this paper, we present a hill-shift learning method of the Hopfield neural network for bipartite subgraph problem. The method uses the Hopfield neural network to get a near-maximum bipartite subgraph, and shifts the local minimum of energy function by adjusts the balance between two terms in the energy function to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm.

In this paper, introducing a stochastic hill-climbing dynamics into an optimal competitive Hopfield network model (OCHOM), we propose a new algorithm that permits temporary energy increases, which helps the OCHOM escape from local minima. In graph theory, a clique is a completely connected subgraph and the maximum clique problem (MCP) is to find a clique of maximum size of a graph. The MCP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. Recently, Galan-Marin et al. proposed the OCHOM for the MCP. It can guarantee convergence to a global/local minimum of energy function, and performs better than other competitive neural approaches. However, the OCHOM has no mechanism to escape from local minima. The proposed algorithm introduces stochastic hill-climbing dynamics which helps the OCHOM escape from local minima, and it is applied to the MCP. A number of instances have been simulated to verify the proposed algorithm.

In this paper, we propose a new parallel algorithm for cellular radio channel assignment problem that can help the expanded maximum neural network escape from local minima by introducing a transient chaotic neurodynamics. The goal of the channel assignment problem, which is an NP-complete problem, is to minimize the total interference between the assigned channels needed to satisfy all of the communication needs. The expanded maximum neural model always guarantees a valid solution and greatly reduces search space without a burden on the parameter-tuning. However, the model has a tendency to converge to local minima easily because it is based on the steepest descent method. By adding a negative self-feedback to expanded maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm then is fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the expanded maximum neural network and the chaotic neurodynamics. Simulations on benchmark problems demonstrate the superior performance of the proposed algorithm over other heuristics and neural network methods.

In this paper, based on maximum neural network, we propose a new parallel algorithm that can escape from local minima and has powerful ability of searching the globally optimal or near-optimum solution for the maximum clique problem (MCP). In graph theory a clique is a completely connected subgraph and the MCP is to find a clique of maximum size of a graph. The MCP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. Lee and Takefuji have presented a very powerful neural approach called maximum neural network for this NP-complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to the local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm.

We present a learning algorithm of the Hopfield neural network for minimizing edge crossings in linear drawings of nonplanar graphs. The proposed algorithm uses the Hopfield neural network to get a local optimal number of edge crossings, and adjusts the balance between terms of the energy function to make the network escape from the local optimal number of edge crossings. The proposed algorithm is tested on a variety of graphs including some "real word" instances of interconnection networks. The proposed learning algorithm is compared with some existing algorithms. The experimental results indicate that the proposed algorithm yields optimal or near-optimal solutions and outperforms the compared algorithms.

The goal of the maximum cut problem is to partition the vertex set of an undirected graph into two parts in order to maximize the cardinality of the set of edges cut by the partition. The maximum cut problem has many important applications including the design of VLSI circuits and communication networks. Moreover, many optimization problems can be formulated in terms of finding the maximum cut in a network or a graph. In this paper, we propose an improved Hopfield neural network algorithm for efficiently solving the maximum cut problem. A large number of instances have been simulated. The simulation results show that the proposed algorithm is much better than previous works for solving the maximum cut problem in terms of the computation time and the solution quality.

A near-optimum parallel algorithm for bipartite subgraph problem using gradient ascent learning algorithm of the Hopfield neural networks is presented. This parallel algorithm, uses the Hopfield neural network updating to get a near-maximum bipartite subgraph and then performs gradient ascent learning on the Hopfield network to help the network escape from the state of the near-maximum bipartite subgraph until the state of the maximum bipartite subgraph or better one is obtained. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds the solution quality is superior to that of best existing parallel algorithm. We also test the proposed algorithm on maximum cut problem. The simulation results also show the effectiveness of this algorithm.

A gradient ascent learning algorithm of the Hopfield neural networks for graph planarization is presented. This learning algorithm uses the Hopfield neural network to get a near-maximal planar subgraph, and increases the energy by modifying parameters in a gradient ascent direction to help the network escape from the state of the near-maximal planar subgraph to the state of the maximal planar subgraph or better one. The proposed algorithm is applied to several graphs up to 150 vertices and 1064 edges. The performance of our algorithm is compared with that of Takefuji/Lee's method. Simulation results show that the proposed algorithm is much better than Takefuji/Lee's method in terms of the solution quality for every tested graph.

In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V,A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u,v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u,v)f(v,w) for any adjacent arcs (u,v) and (v,w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.

Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S 2).Next we consider the d2-transmission number sequence so that the distance function is defined by a special convex function.