The management of resources in reconfigurable systems is one of the most critical factors concerned deeply with the performance of dynamic reconfigurable systems. There are several algorithms for managing the empty sp...
详细信息
ISBN:
(纸本)9780769537573
The management of resources in reconfigurable systems is one of the most critical factors concerned deeply with the performance of dynamic reconfigurable systems. There are several algorithms for managing the empty space of reconfigurable systems, among which the basic Scan Line Algorithm (SLA)[1] is a relative efficient one. However SLA suffers from two problems: redundancy and duplication. To solve duplication, the improved Scan Line Algorithm (ISLA) is proposed in [1]. However the redundancy problem is remained. Therefore, we are motivated to over come this problem and propose an enhanced algorithm called ESLA based on SLA. ESLA solves problems of both redundancy and duplication. Further, Simulation experiments show that the performance of ESLA is better than ISLA.
One of the most important abstractions for designing distributed programs is the broadcast facility. In this paper, we study the interconnection of distributed message passing systems. We have shown that totally order...
详细信息
One of the most important abstractions for designing distributed programs is the broadcast facility. In this paper, we study the interconnection of distributed message passing systems. We have shown that totally ordered systems cannot be properly interconnected in any form. However, we have provided a simple protocol to properly interconnect FIFO ordered systems. (C) 2007 Elsevier B.V. All rights reserved.
Modular exponentiation is a frequent task, in particular for many cryptographic applications. To accelerate modular exponentiation for very large integers one may use repeated squaring. which is based on representing ...
详细信息
Modular exponentiation is a frequent task, in particular for many cryptographic applications. To accelerate modular exponentiation for very large integers one may use repeated squaring. which is based on representing the exponent in the standard binary numeration system. We show here that for certain applications, replacing the standard system by one based on Fibonacci numbers may yield a new line of time/space tradeoffs. (C) 2007 Elsevier B.V. All rights reserved.
The guided tree edit distance problem is to find a minimum cost series of edit operations that transforms two input forests F and G into isomorphic forests F' and G' such that a third input forest H is include...
详细信息
The guided tree edit distance problem is to find a minimum cost series of edit operations that transforms two input forests F and G into isomorphic forests F' and G' such that a third input forest H is included in F' (and G'). The edit operations are relabeling a vertex and deleting a vertex. We show efficient algorithms for this problem that are faster than the previous algorithm for this problem of Peng and Ting [Z. Peng, H. Ting, Guided forest edit distance: Better structure comparisons by using domain-knowledge, in: Proc. 18th Symposium on Combinatorial Pattern Matching (CPM), 2007, pp. 28-39]. (C) 2008 Elsevier B.V. All rights reserved.
The reconstruction of an ultrametric tree from a distance matrix is a very frequent subproblem in clustering or reconstructing evolutionary trees, both are common problems in Bioinformatics. In his famous book, Gusfie...
详细信息
The reconstruction of an ultrametric tree from a distance matrix is a very frequent subproblem in clustering or reconstructing evolutionary trees, both are common problems in Bioinformatics. In his famous book, Gusfield presented a very simple, but not time-optimal recursive algorithm for this problem. We show that a simple modification of Gusfield's algorithm allows a time-optimal solution. (C) 2008 Elsevier B.V. All rights reserved.
Given a query point, locating its nearest neighbor among a set of objects is a fundamental problem arising in many application fields, including computer graphics, pattern recognition, robot motion planning, informati...
详细信息
Given a query point, locating its nearest neighbor among a set of objects is a fundamental problem arising in many application fields, including computer graphics, pattern recognition, robot motion planning, information retrieval, machine learning, and data mining. For example, in computer animation, collision detection tests usually boil down to checking whether a query point intersects any object in the scene or not. The most widely studied version of this problem is to find the nearest neighbor of a query point among a set of points under the Euclidean distance.
The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or ...
详细信息
The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or consider only two sequences. Recently, with the rise of whole-genome duplication research, the doubly conserved synteny relationship among three sequences should be considered. It is a brand new model to find a merging way for understanding the interleaving relationship of sequences. Here, we define the merged LCS problem for measuring the interleaving relationship among three sequences. An 0(113) algorithm is first proposed for solving the problem, where it is the sequence length. We further discuss the variant version of this problem with the block information. For the blocked merged LCS problem, we propose an algorithm with time complexity O(n(2)m), where in is the number of blocks. An improved O(n(2)+nm(2)) algorithm is further proposed for the same blocked problem. (c) 2007 Published by Elsevier B.V.
We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF[i] gives the length of the longest factor of w starting at pos...
详细信息
We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF[i] gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size. (C) 2007 Elsevier B.V. All rights reserved.
In this paper we give approximation algorithms and inapproximability, results for various asymmetric k-center with minimum coverage problems. In the k-center with minimum coverage problem, each center is required to s...
详细信息
In this paper we give approximation algorithms and inapproximability, results for various asymmetric k-center with minimum coverage problems. In the k-center with minimum coverage problem, each center is required to serve a minimum number of clients. These problems have been studied by Lim et al. [A. Lim, B. Rodrigues, F. Wang, Z. Xu, k-center problems with minimum coverage, Theoret. Comput. Sci. 332 (1-3) (2005) 1-17] in the symmetric setting. (c) 2007 Elsevier B.V. All rights reserved.
Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively. be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest c...
详细信息
Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively. be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl + min{p(1),p(2)}) time, where p1 and p2 denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl, km}) and outperforms the time bounds O(kl log kl) or O((k + l + q) log (k + l + q)) for some cases, where q denotes the number of matched blocks. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论