Search

Abstract: The interconnection network considered in this paper is the folded hypercube that is an attractive variance of the well-known hypercube. The folded hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. In this paper, we study the path embedding aspects, bipanconnectivity and -panconnectivity, of the -dimensional folded hypercube. A bipartite graph is bipanconnected if each pair of vertices and are joined by the bipanconnected paths that include a path of each length satisfying and is even, where is the number of vertices, and denotes the shortest distance between and . A graph is -panconnected if each pair of vertices and are joined by the paths that include a path of each length ranging from to . In this paper, we introduce a new graph called the Path-of-Ladders. By presenting algorithms to embed the Path-of-Ladders into the folded hypercube, we show that the -dimensional folded hypercube is bipanconnected for is an odd number. We also show that the -dimensional folded hypercube is strictly -panconnected for is an even number. That is, each pair of vertices are joined by the paths that include a path of each length ranging from to ; and the value reaches the lower bound of the problem. [Copyright &y& Elsevier]

Abstract: In the -set agreement problem, each process (in a set of processes) proposes a value and has to decide a proposed value in such a way that at most different values are decided. While this problem can easily be solved in asynchronous systems prone to process crashes when , it cannot be solved when . For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the -set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases (consensus) and (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for -set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted , that is such that (the weakest class for ), and (the weakest class for ). (b) The second is an investigation of the structure of that shows that is the combination of two failure detector classes (that is new) and (they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the -set agreement problem in message-passing systems. (d) Finally, the last contribution is a -based algorithm that solves the -set agreement problem. This algorithm provides us with a new algorithmic insight on the way the -set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for -set agreement in message-passing systems. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for convex polygon decomposition around a given set of locations. Given an -vertex convex polygon and a set of points positioned arbitrarily inside , the task is to divide into equal-area convex parts, each containing exactly one point of . The algorithm runs in time . [Copyright &y& Elsevier]

Abstract: Let be a connected graph such that each edge is weighted by nonnegative real . Let be a vertex designated as a source, be a positive integer, and be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition of and a set of trees of such that consists of at most terminals and each spans . The objective is to minimize , where denotes the sum of weights of all edges in . In this paper, we propose a -approximation algorithm to the CMTR, where is the best achievable approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word and nonempty words satisfying , the minimal local period associated with the factorization is the length of the shortest square at position . The critical factorization theorem shows that for any word, there is always a factorization whose minimal local period is equal to the minimal period (or global period) of the word. Crochemore and Perrin presented a linear time algorithm (in the length of the word) that finds a critical factorization from the computation of the maximal suffixes of the word with respect to two total orderings on words: the lexicographic ordering related to a fixed total ordering on the alphabet, and the lexicographic ordering obtained by reversing the order of letters in the alphabet. Here, by refining Crochemore and Perrin’s algorithm, we give a version of the critical factorization theorem for partial words (such sequences may contain “do not know” symbols or “holes”). Our proof provides an efficient algorithm which computes a critical factorization when one exists. Our results extend those of Blanchet-Sadri and Duncan for partial words with one hole. A World Wide Web server interface at http://www.uncg.edu/mat/research/cft2/ has been established for automated use of the program. [Copyright &y& Elsevier]