52830861
A Coarse-Grained Parallel Algorithm for Maximal Cliques in Circle Graphs
We present a parallel algorithm for generating the maximal cliques of a circle graph with n vertices and m edges. We consider the Coarse-Grained Multicomputer Model (CGM) and show that the proposed algorithm requires O(log p) communication rounds, where p is the number of processors, independent of n. The main contribution is the use of a new technique based on the unrestricted depth search for the design of CGM algorithms.
29123307
Efficient Parallel Implementation of Transitive Closure of Digraphs
Based on a CGM/BSP parallel algorithm for computing the transitive closure of an acyclic directed graph (digraph), we present a modified version that works for any digraph and show very promising implementation results. The original CGM/BSP algorithm for acyclic digraphs uses a linear extension labeling of the vertices. With this labeling, the original algorithm can be shown to require log p + 1 communication rounds, where p is the number of processors. The modified CGM/BSP algorithm works for any digraph and does not use the linear extension labeling. In theory the modified version no longer guarantees the O(log p) bound on the number of communication rounds, as shown by an artificially elaborated example that requires more than log p + 1 communication rounds. In practice, however, all the graphs tested use at most log p + 1 communication rounds. The implementation results are very promising and show the efficiency and scalability of the proposed modified algorithm, and compare favorably with other parallel implementations.
17543628
Efficient Implementation of the BSP/CGM Parallel Vertex Cover FPT Algorithm
In many applications NP-complete problems need to be solved exactly. One promising method to treat some intractable problems is by considering the so-called Parameterized Complexity that divides the problem input into a main part and a parameter. The main part of the input contributes polynomially on the total complexity of the problem, while the parameter is responsible for the combinatorial explosion. We consider the parallel FPT algorithm of Cheetham et al. to solve the k-Vertex Cover problem, using the CGM model. Our contribution is to present a refined and improved implementation. In our parallel experiments, we obtained better results and obtained smaller cover sizes for some input data. The key idea for these results was the choice of good data structures and use of the backtracking technique. We used 5 graphs that represent conflict graphs of amino acids, the same graphs used also by Cheetham et al. in their experiments. For two of these graphs, the times we obtained were approximately 115 times better, for one of them 16 times better, and, for the remaining graphs, the obtained times were slightly better. We must also emphasize that we used a computational environment that is inferior than that used in the experiments of Cheetham et al.. Furthermore, for three graphs, we obtained smaller sizes for the cover.
13919002
Efficient embeddings into the hypercube using matrix transformations
The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embedding the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods, based on matrix transformations, for e~ciently embedding different networks into the hypercube (binary n-cube). First, we use this method to embed r-ary m-cubes into a binary n-cube of the same size with dilation 1. While our method has the same dilation as traditional methods using rejlected Gray code, it has the additional property of making the layout of the binary n-cube more suitable for divide-and-conquer algorithms. Second, we use our matrix transformation method to optimally embed hierarchical interconnection networks into the binary n-cube which we would not achieve using rejlected Gray code embedding. Thus, this embedding method has signi$cant practical importance in enhancing the capabilities of the hypercube..
14651264
Computing Maximum Subsequence in Parallel
The maximum subsequence problem finds the contiguous subsequence of n real numbers with the highest sum. This is an important problem that arises in several contexts in Computational Biology in the analysis of DNA or protein sequences. The maximum subsequence problem of n given scores can be solved sequentially in O(n) time. In this paper we present an efficient BSP/CGM parallel algorithm that requires a constant number of communication rounds. In the proposed algorithm, the input is partitioned equally among the processors and the sequence stored on each processor is reduced to only five numbers. This reduction is crucial as it allows all the resulting values to be concentrated on a single processor which runs an adaptation of the sequential algorithm to obtain the result. The amount of data transmitted is 5p where p is the number of processors, thus independent of the input size n. The good performance of the parallel algorithm is confirmed by experimental results run on a 64-node Beowulf parallel computer, giving almost linear speedup. Topic of interest: Algorithms and Software Tools for Computational Molecular Biology
17321479
Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach
Abstract We present O(n3) heuristic algorithms for multiple/ simple PLA folding, which also apply to the matrix layout problem. Our heuristic is based on a new approach, where both problems are shown to be composed by a permutation step followed by a compaction step. Therefore we are able to show that the exponential complexity of the problem stems from the permutation step—where a good configuration is searched—, since the compaction step—where the actual folding takes place—is optimally solved in polynomial time. We discuss bounds on the distance of the obtained solution to the optimal and give sufficient conditions for the solution to be optimal. Verification of the sufficient conditions constitutes part of the proposed algorithms, and is in fact used to construct the heuristic solution. An example showing the multiple folding of a 58 × 19 PLA produced by the proposed algorithm is presented.
2193712
Similarity Joins of Text with Incomplete Information Formats
Similarity join over text is important in text retrieval and query. Due to the incomplete formats of information representation, such as abbreviation and short word, similarity joins should address an asymmetric feature that these incomplete formats may contain only partial information of their original representation. Current approaches, including cosine similarity with q-grams, can hardly deal with the asymmetric feature of similarity between words and their incomplete formats. In order to find this type of incomplete format information with asymmetric features, we develop a new similarity join algorithm, namely IJoin. A novel matching scheme is proposed to identify the overlap between two entities with incomplete formats. Other than q-grams, we reconnect the sequence of words in a string to reserve the abbreviated information. Based on the asymmetric features of similar entities with incomplete formats, we adopt a new similarity function. Furthermore, an efficient algorithm is implemented by using the join operation in SQL, which reduces pairs of tuples in similarity comparison. The experimental evaluation demonstrates the effectiveness and the efficiency of our approach.
701055
Practical Security Improvement of PKCS#5
A public key infrastructure (PKI) is being deployed in a field of network security. PKCS#5 is one of the most popular standards in PKI framework, intended for the practical implementation of password-based cryptography. So, the PKCS#5 encryption must be useful for general software applications within multimedia systems. However, it has a critical weak point in terms of security such as being vulnerable to off-line attacks due to the password-derived encryption key. In this paper, we observe a practical and simple method to improve security of the PKCS#5 encryption without modifying the installed base. The idea is to hide a salt by exploiting several existing schemes.