16976049
Efficient Broadcasting in Wormhole-Routed Multicomputers: A Network-Partitioning Approach
In this paper, a network-partitioning approach for one-to-all broadcasting on wormhole-routed networks is proposed. To broadcast a message, the scheme works in three phases. First, a number of data-distributing networks (DDNs), which can work independently, are constructed. Then the message is evenly divided into submessages, each being sent to a representative node in one DDN. Second, the submessages are broadcast on the DDNs concurrently. Finally, a number of data-collecting networks (DCNs), which can work independently too, are constructed. Then, concurrently on each DCN, the submessages are collected and combined into the original message. Our approach, especially designed for wormhole-routed networks, is conceptually similar but fundamentally very different from the traditional approach of using multiple edge-disjoint spanning trees in parallel for broadcasting in store-and-forward networks. One interesting issue is on the definition of independent DDNs and DCNs, in the sense of wormhole routing. We show how to apply this approach to tori, meshes, and hypercubes. Thorough analyses and comparisons based on different system parameters and configurations are conducted. The results do confirm the advantage of our scheme, under various system parameters and conditions, over other existing broadcasting algorithms.
44408883
Hamiltonian-laceability of star graphs
29920941
Counting Clique Trees and Computing Perfect Elimination Schemes in Parallel
Abstract In a previous result, the authors showed that a clique tree of a chordal graph can be constructed in O(log n ) parallel computing time with O( n 3 ) processors on CRCW PRAM, where n is the number of nodes of the graph. In this paper, it will be shown that this result can be extended in two ways. First, we show that from the parallel clique tree constructing algorithm, we can derive an exact formula of counting clique trees of a labeled connected chordal graph. Next, we show that a perfect elimination scheme of a chordal graph can be computed in O(log n ) time with O( n 2 ) processors on CREW PRAM once a clique tree of the graph is given. This implies that a perfect elimination scheme of a chordal graph can be computed in O(log n ) time with O( n 3 ) processors on CRCW PRAM.
45928902
An Efficient Parallel Strategy for Computing K-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees
In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(GK), in 2-trees. Based on this result, we can also computeR(GK) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(logn) time withC(m,n) processors on a CRCW PRAM, whereC(m,n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.
17202338
Fault-Free Hamiltonian Cycles in Faulty Arrangement Graphs
The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-k=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously, the arrangement graph has proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is Hamiltonian when 1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k)-2, or 2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or 3) k/spl ges/2, n-k/spl ges/3, and |F/sub e/|/spl les/k, or 4) n-k/spl ges/3 and |F/sub v/|/spl les/n-3, or 5) n-k/spl ges/3 and |F/sub v/|+|F/sub e/|/spl les/k. Besides, for A/sub n,k/ with n-k=2, we construct a cycle of length at least 1) [n!/(n-k!)]-2 if |F/sub e/|/spl les/k-1, or 2) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub v/|/spl les/k-1, or 3) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub e/|+|F/sub v/|/spl les/k-1, where [n!/(n-k)!] is the number of nodes in A/sub n,k/.
10538824
Parallel Decomposition of Generalized Series-Parallel Graphs
Generalized series-parallel (GSP) graphs belong to the class of decomposable graphs which can be represented by their decomposition trees. Given a decomposition tree of a GSP graph, there are many graph-theoretic problems which can be solved efficiently. An efficient parallel algorithm for constructing a decomposition tree of a given GSP graph is presented. It takes O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find connected components of a graph with in edges and n vertices in logarithmic time. Based on our algorithmic results, we also derive some properties for GSP graphs, which may be of interest in and of themselves.
641485
Mapping XML and relational schemas with Clio
Merging and coalescing data from multiple and diverse sources into different data formats continues to be an important problem in modern information systems. Schema matching (the process of matching elements of a source schema with elements of a target schema) and schema mapping (the process of creating a query that maps between two disparate schemas) are at the heart of data integration systems. We demonstrate Clio, a semi-automatic schema mapping tool developed at the IBM Almaden Research Center. In this paper, we showcase Clio's mapping engine which allows mapping to and from relational and XML schemas, and takes advantage of data constraints in order to preserve data associations.
13477825
A HYBRID GENETIC ALGORITHM FOR OPTICAL ORTHOGONAL CODE CONSTRUCTION
Optical orthogonal codes (OOCs) are used to uniquely identify stations within an optical code division multiple access (CDMA) local area network (LAN). Previous efforts in constructing OOCs have focused on the use of deterministic techniques, which relied heavily on the use of Galois fields. These techniques severely restrict the availability of the resulting OOCs. This paper considers an evolutionary approach by proposing a hybrid genetic algorithm (hGA) as a flexible technique to construct OOCs. This hGA uses the simulated annealing (SA) method to generate its initial population. The effectiveness of the proposed hGA for OOC construction is demonstrated in two stages. First, we show that the SA-generated initial population is better than the randomly generated initial population in terms of fitness. Due to this, the hGA is able to converge on average two times faster compared to the use of the GA-only scheme. Second, we compare the code availability and performance of the hGA-constructed OOCs (hGA OOCs) against that of three other OOCs. Through these comparisons, we show why the proposed hGA is a more flexible technique for constructing OOCs with higher availability and better performance.
39997093
Performance of an Ant Colony Optimization (ACO) Algorithm on the Dynamic Load-Balanced Clustering Problem in Ad Hoc Networks
This paper examines the performance of a recently proposed ACO algorithm when applied to the problem of constructing load-balanced clusters in ad hoc networks with node mobility. Performance, in this context, is measured in terms of the magnitude of change in solution quality after nodes move, and reactivity. Reactivity refers to the number of cycles ACO takes to recover from any degradation in solution quality resulting from node movements. Empirical results on 16 problem instances of various sizes revealed a positive correlation
12331697
The Clio project: managing heterogeneity
Clio is a system for managing and facilitating the complex tasks of heterogeneous data transformation and integration. In Clio, we have collected together a powerful set of data management techniques that have proven invaluable in tackling these difficult problems. In this paper, we present the underlying themes of our approach and present a brief case study.
30879352
An Ant Colony Optimization Approach to the Degree-Constrained Minimum Spanning Tree Problem
This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO’s for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem. The effectiveness of the proposed algorithm is demonstrated through two kinds of data set: structured hard (SHRD) complete graphs and misleading (M-graph) complete graphs. Empirical results show that ACO performs competitively with other approaches based on evolutionary algorithm (EA) on certain instance set problem.