Abstract: We present a hybrid model named HRKPG that combines the random‐key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random‐key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality.

This paper proposes a blind watermarking algorithm based on the significant difference of wavelet coefficient quantization for copyright protection. Every seven nonoverlap wavelet coefficients of the host image are grouped into a block. The largest two coefficients in a block are called significant coefficients in this paper and their difference is called significant difference. We quantized the local maximum wavelet coefficient in a block by comparing the significant difference value in a block with the average significant difference value in all blocks. The maximum wavelet coefficients are so quantized that their significant difference between watermark bit 0 and watermark bit 1 exhibits a large energy difference which can be used for watermark extraction. During the extraction, an adaptive threshold value is designed to extract the watermark from the watermarked image under different attacks. We compare the adaptive threshold value to the significant difference which was quantized in a block to determine the watermark bit. The experimental results show that the proposed method is quite effective against JPEG compression, low-pass filtering, and Gaussian noise; the PSNR value of a watermarked image is greater than 40 dB.

In this paper, we present a constant time algorithm for solving three dimensional block-based medial axis transform (3D BB-MAT, for short) on the array with reconfigurable optical buses (AROB). The main contribution of this work is to exploit the dominance counting method for solving the 3D BB-MAT that was never done previously in the literature. With the advantages of both optical transmission and electronic computation on the AROB model, the constant algorithm is proposed for the medial axis transform of a 3D N x N x N binary image on a 4D AROB using N^4 processors. To the best of our knowledge, this presented result of the dominance counting technique for medial axis transform of block-based is the best O(1) time algorithm known.

Clustering techniques are usually used in pattern recognition, image segmentation and object detection. For N patterns and k centers each with M features, in this paper, we first design an O(kM) time optimal parallel algorithm for one pass process of clustering with the k-means method on a linear array of processors with a wider bus network using N/sup 1+1/c/ processors with one bus network, where c is any constant and c/spl ges/1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN/sup 1+1/c/ and kMN/sup 1+1/c/ processors with M row and MN row bus networks, respectively. These results improve the best known bounds and achieve cost optimal in their time and processor complexities.

The generalized Fibonacci cubes (abbreviated to GFCs) were recently proposed as a class of interconnection topologies, which cover a spectrum ranging from regular graphs such as the hypercube to semiregular graphs such as the second order Fibonacci cube. It has been shown that the kth order GFC of dimension n+k is equivalent to an n-cube for 0/spl les/n

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N/spl times/N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively.

A cross-bridge reconfigurable array of processors is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm. Based on this architecture, several O(1) time basic operations such as the transpose, the untranspose, the shift, the unshift and the prefix sum of a binary sequence are first proposed. Then, these basic operations can be used to find the kth smallest element of N m bits unsigned integers in O(m) time using N processors and to sort N data items in O(1) time using O(N/sup 5/3/) processors instead of using O(N/sup 2/) processors as those proposed by other researchers.>

In this paper, instead of using the base-2 number system, we use a base-m number system to represent the numbers used in the proposed algorithms. Such a strategy can be used to design an O(T) time, T=[log/sub m/N]+1, prefix sum algorithm for a binary sequence with N-bit on a cross-bridge reconfigurable array of processors using N processors, where the data bus is m-bit wide. Then, this basic operation can be used to compute the histogram of an n/spl times/n image with G gray-level value in constant time using G/spl times/n/spl times/n processors, and compute the Hough transform of an image with N edge pixels and n/spl times/n parameter space in constant time using n/spl times/n/spl times/N processors, respectively. This result is better than the previously known results. Also, the execution time of the proposed algorithms is tunable by the bus bandwidth.>

This paper makes an improvement of computing the list ranking and some related problems on a reconfigurable array of processors (abbreviated to RAP) with wider bus networks by increasing the bus width between processors. Based on such an architecture and a base-n system technique, a constant time basic operation is first introduced for computing the prefix modular n and prefix division n computations of an N-bit binary sequence on a linear RAP using N processors. Then, several fundamental problems can be solved in a constant time on a RAP using N/sup 1+1/c/ processors with N/spl times/N/sup 1+1/c/ bus networks and each bus network with N/sup 1/c/-bit, where c is a constant and e/spl ges/1. These algorithms include the prefix sum of N integers problem, the weight list ranking problem, the Euler tour problem and the tree recursions problem, respectively. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.

We show that determine the maximum number of vertex connectivity, test k-vertex connectivity and determine the maximum number of vertex disjoint I_s - l_t paths of interval graphs can be solved either in O(log n) time using O{n) processors for the Unsorted case or in O{logn) time using O{n/logn) processors for the sorted case, and find k-vertex disjoint I_s - I_t paths of interval graphs can be solved in O{k logn) time using O{n^{2}/logn) processors on the EREW PRAM model, respectively. All parallel algorithms are optimal with respect to the time-processor product except the last one.

A reconfigurable array of processors (RAP) is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm.