Search

In this work, we assume a geographic area populated by tiny sensors, each perhaps no larger than a dime. In order to save their energy, the sensors spend most of their lifetime in sleep mode and wake up for short periods of time to participate in various tasks supportive of the overall mission of the network. We assume that the tasks to be performed stipulate QoS parameters expressed in terms of the minimum number of sensors that need to monitor their sensing area. Since only awake sensors participate in tasks, the Effective Sensor Density (ESD), defined as the density of awake sensors, is an important network parameter that obviously depends on the sleep schedules adopted in the network. The first main contribution of this work is to provide a mathematical analysis of ESD from the perspective of the monitored events. We also provide design guidelines to determine deployment-time sensor density and an associated sleep schedule that probabilistically keeps the ESD at a level needed by QoS requirements. We also propose a fully distributed sleep schedule which adaptively adjusts the duty cycles of sensors within the same sensing area based on the relative difference in their remaining energy budget. The main advantage of the proposed adaptive scheme is to balance energy consumption among sensors, thus promoting the functional longevity of the sensor network without adversely affecting the ESD.

One of the side-effects of the climate changes that are upon us is that infectious diseases are adapting, evolving and spreading to new geographic regions. It is, therefore, imperious to develop epidemic models that shed light on the interplay between the dynamics of the spread of infectious diseases and the combined effects of various vaccination and prevention regimens. With this in mind, in this work we propose a epidemic model operating on a large population; we restrict our attention to strains of infectious diseases that resist treatment. The time-dependent epidemic accounts, among others, for the effects of improved sanitation, education and vaccination. Our first main contribution is to derive the time-dependent probability mass function of the number of infected individuals in such a system. Our derivation does not use probability generating functions and partial differential equations. Instead, we develop an iterative solution that is conceptually simple and easy to implement. Somewhat surprisingly, the epidemic model also provides insight into various stochastic phenomena noticed in sociology, macroeconomics, marketing, transportation and computer science. Our second main contribution is to show, by extensive simulations, that suitably instantiated, our epidemic model be used to model phenomena describing the adoption of durable consumer goods, the spread of AIDS and the dissemination of mobile worm spread.

PurposeThe purpose of this paper is to model an important aspect of the problem of sensor information integration that arises in wireless communications, where N sensors try to communicate with a receiver using a single un‐shareable radio channel. If several sensors transmit at the same time, their transmissions collide at the receiver resulting in garbled messages and the need for re‐transmission. This is highly undesirable since the sensors are energy‐constrained and the radio interface is known to be the most significant source of energy expenditure. Consequently, it is of paramount importance to design arbitration protocols that are highly efficient in stamping out collisions and that are, at the same time, as lightweight as possible.Design/methodology/approachThe receiver advertises a time division multiple access (TDMA) frame consisting of n slots, numbered from 1 to n, where n is an application‐dependent parameter. Each sensor generates uniformly at random, and independently of other sensor, an integer i between 1 and n and transmits in the i‐th slot of the TDMA frame. If two or more sensors are transmitting in the same slot their messages will be lost to collision. Similarly, slots that carry no transmission are wasted. The authors model the arbitration strategy discussed above as a Bose‐Einstein occupancy problem where N indistinguishable balls are thrown at random into n distinguishable bins and all distinguishable outcomes are considered to be equally likely.FindingsIn this paper the authors present a distributed probabilistic mechanism that aims to arbitrate between several competing requests by various sensors for the radio channel. The mechanism is simple, energy‐efficient and does not rely on the existence of unique sensor identifiers (IDs).Originality/valueThe Bose‐Einstein occupancy model presented in this paper will help the receiver to tailor an appropriate number of timeslots in TDMA frame during the integration process, such that collisions are minimized, and hence integration between sensors can be done effectively.

In numerous applications of wireless sensor networks (WSN), the reliability of the data collected by sensors is cast as specific QoS requirements expressed in terms of the minimum number of sensors needed to perform various tasks. Designing a long-lived sensor network with reliable performance has always been challenging due to the modest nonrenewable energy budget of individual sensors. In such a context, energy-unaware task management protocols may result in uneven expenditure of sensor energy by assigning uneven workloads to sensors. This, in turn, often translates into reduced sensor density around those heavily loaded sensors and may, eventually, lead to the creation of energy holes that partition the network into disconnected islands. To avoid these problems and to promote network longevity, we propose two energy-aware task management protocols: our first protocol is centralized, while the second one is fully distributed. The proposed protocols assign tasks to sensors based on their remaining energy so that energy expenditure among neighboring sensors is almost even. We compare the reliable lifetime of the network achieved by assigning tasks to sensors using the proposed protocols against optimal task assignment and also against energy-unaware protocols. Extensive simulation results have revealed that the performance of the proposed protocols is very close to that of the optimal task assignment. Furthermore, our simulation has shown that the proposed protocols can increase the functional longevity of the network by about 16 percent.

PurposeThe past decade has witnessed a growing interest in vehicular networking and its myriad applications. The initial view of practitioners and researchers was that radio‐equipped vehicles can keep the drivers informed about potential safety risks and can enhance their awareness of road conditions and traffic‐related events. This conceptual paper seeks to put forth a novel vision, namely that advances in vehicular networks, embedded devices, and cloud computing can be used to set up what are known as vehicular clouds (VCs).Design/methodology/approachThe paper suggests that VCs are technologically feasible and that they are likely to have a significant societal impact.FindingsThe paper argues that at least in some of its manifestations, the ideas behind VCs are eminently implementable under present day technology. It is also expected that, once adopted and championed by municipalities and third‐party infrastructure providers, VCs will redefine the way in which pervasive computing and its myriad applications is thought of.Research limitations/implicationsThis is a new concept for which a small‐scale prototype is being built. No large‐scale prototype exists at the moment.Practical implicationsVCs are a novel concept motivated by the realization of the fact that, most of the time, the tremendous amount of computing and communication resources available in vehicles is underutilized. Putting these resources to work in a meaningful way should have a significant societal impact.Social implicationsThe main goal of this paper is to introduce and promote the concept of VCs, a non‐trivial extension, along several dimensions, of the by‐now “classic” cloud computing. The paper shows that the concept of VCs is feasible as of today – at least in some of its manifestations – and that it can have a significant societal impact in the years to come.Originality/valueThe idea of a VC is novel and so are the potential applications that are discussed in the paper.

Phenomenal advances in nano-technology and packaging have made it possible to develop miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. It is expected that these small devices, referred to as sensors, will be mass-produced and deployed, making their production cost negligible. Due to their small form factor and modest non-renewable energy budget, individual sensors are not expected to be GPS-enabled. Moreover, in most applications, exact geographic location is not necessary, and all that the individual sensors need is a coarse-grain location awareness. The task of acquiring such a coarse-grain location awareness is referred to as training. In this paper, two scalable energy-efficient training protocols are proposed for massively-deployed sensor networks, where sensors are initially anonymous and unaware of their location. The training protocols are lightweight and simple to implement; they are based on an intuitive coordinate system imposed onto the deployment area which partitions the anonymous sensors into clusters where data can be gathered from the environment and synthesized under local control.

Sensor networks are expected to evolve into long-lived, open, ubiquitous, multi-purpose networked systems. We propose a new concept called AutoNomouS netWorked sEnsoR system (ANSWER) whose mission is to provide in situ users with real-time, secure information that enhances their situational and location awareness. To the best of our knowledge, solutions that accomplish this goal do not yet exist. ANSWER finds immediate applications to both overt and covert operations ranging from tactical battlefield surveillance to crisis management and homeland security. The architectural model of ANSWER is composed of a large number of sensors and of a set of (mobile) aggregation-and-forwarding nodes that organize and manage the sensors in their vicinity. In this paper we present the main features that enable ANSWER to effectively and efficiently provide secure, QoS-aware information services to in situ mobile users; namely, secure dynamic task-based networking and in-network storage to support application-level tasks and queries (each specified with desired QoS and security attributes), while hiding network-level details; and a model-based methodology exploiting QoS and security trade-offs for smart AFN mobility subject to application and network requirements and constraints. This new concept is in sharp departure from the prevalent view in NSS design that networking is independent of the task(s) at hand and information processing and storage are, primarily, the responsibility of remote entities.

In a dimensional problem, the transformation of a graph into its linear network can be viewed as a transition involving demand and supply. A connected graph represents the demand flows between the components in the graph while the network supporting it is the resource or capacity links for supporting the demand volumes. The transformation involves a mapping from the graph to its network to satisfy certain performance metrics. In this work, we propose a model for transforming a connected graph to its linear network model in the form of a single-row routing network. The main objective is to provide an optimum routing network that minimizes the congestion. In this technique, the given graph is first partitioned into several disjoint cliques using the Hopfield neural network using our model called AdCliq. From the cliques, a set of intervals derived from the zones are obtained through the matching nodes in the single-row axis. The intervals are then mapped into a network of non-crossing nets using our previously developed tool called ESSR. The network is optimal in terms of minimum street congestion and number of doglegs, and this provides a reasonably good step towards the overall solution to the demand-supply problem.

A complete graph is a fully-connected graph where every node is adjacent to all other nodes in the graph. Very often, many applications in science and engineering are reducible to this type of graph. Hence, a simplified form of a complete graph contributes in providing the solutions to these problems. In this paper, we present a technique for transforming a complete graph into a single-row routing problem. Single-row routing is a classical technique in the VLSI design that is known to be NP-complete. We solved this problem earlier using a method called ESSR, and, the same technique is applied to the present work to transform a complete graph into its single-row routing representation. A parallel computing model is proposed which contributes in making the problem modular and scalable. We also discuss the application of this work on the channel assignment problem in the wireless cellular telephone networks.

In recent years, a significant number of clustering schemes have been proposed in the literature. Most of them treat cluster initialization and cluster maintenance differently as if they were two entirely different undertakings. The main contribution of this work is a unifying way of looking at clustering in MANET. We make an important point: there is no difference between cluster initialization and cluster maintenance, and one algorithm should gracefully blend into the other. To illustrate the feasibility of this concept, we propose a novel tree-based clustering algorithm for MANET based on a number of properties of diameter-2 graphs. The algorithm is cluster-centric and, unlike the vast majority of algorithms in the literature, works in the presence of node mobility. Extensive simulation results show the effectiveness of our algorithm when compared to other clustering schemes proposed in the recent literature. Copyright © 2004 John Wiley & Sons, Ltd.

The fully connected network possesses extremely good topological, fault-tolerant, and embedding properties. However, due to its high degree, the fully connected network has not been an attractive candidate for building parallel computers. On the other hand, tree-based networks are popular as parallel computer networks, even though they suffer from poor fault-tolerance and embedding properties. The hierarchical cliques interconnection network described in this paper incorporates positive features of the fully connected network and the tree network. In other words, the hierarchical cliques possess such desirable properties as low diameter, low degree, self routing, versatile embedding, good fault-tolerance and strong resilience. Hierarchical cliques can efficiently embed most important networks and possess a scalable, modular structure. Further, by combining hierarchical cliques with fat trees congestion in the upper levels can be alleviated.

The problem of merging two intransitive sorted sequences (that is, to generate a sorted total order without the transitive property) is considered. A cost-optimal parallel merging algorithm is proposed under the EREW PRAM model. This algorithm has a run time of O( log 2 n) using O(n/ log 2 n) processors. The cost-optimal merge in the strong sense is still an open problem.

With the increase in global wireless communication, there is a need for efficient network management strategies. Location management in a mobile network involves keeping track of mobile host (MH) cell locations. MHs perform location updates to inform the network of their location. When a call arrives for an MH, the network uses its last known cell location and a paging strategy to find that host. Current location management techniques do not consider host-mobility patterns or call arrival rates. This paper describes a selective update strategy that is modeled on the characteristics of a network, such as, topology, host mobility patterns and connection request rates. Then, a genetic algorithm is used to solve the location management problem that involves the search of a large solution space. The aim of the work is to determine whether genetic algorithms can be applied successfully to solve this problem, and to evaluate their efficiency in solving this class of optimization problems. Results from the selective update strategy show improvements over alternative algorithms. The location management optimization problem is shown to be well adapted to the workings of the genetic algorithm. The proposed solution also saves power, processing time, and network bandwidth.

This paper presents ESSR (Enhanced Simulated annealing for Single-row Routing) model for solving the single-row routing problem. The main objective in this problem is to produce a realization that minimizes both the street congestion and the number of doglegs. Simulated annealing (SA) is a stochastic, hill-climbing and gradient-descent technique based on the statistical properties of particles undergoing thermal annealing. By performing slow cooling, the nets in the single-row routing problem align themselves according to a configuration with the lowest energy. The model has been known to produce reasonably good solutions for many NP-complete optimization problems, such as the single-row routing problem. In ESSR, our strategy is to minimize both the street congestion and the number of interstreet crossings (doglegs) by expressing a single energy function as their collective properties. This objective is achieved by representing the energy as the absolute sum of the heights of the net segments. To speed up convergence, we pivot the street congestion value while having the energy drops directly proportional to the number of doglegs. This action has the effect of minimizing the number of doglegs as the energy stabilizes. Our simulation work on ESSR produces optimal results in most cases for both the street congestion and the number of doglegs. Our experimental results compare well against results obtained from our earlier model (SRR-7) and two other methods reported in the literature.

We show that a large variety of NP-complete problems can be solved efficiently for graphs with ‘few’ P 4 's. We consider domination problems (domination, total domination, independent domination, connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. We show that all these problems can be solved in linear time for the class of ( q , q −4)-graphs, for every fixed q . These are graphs for which no set of at most q vertices induces more than q −4 different P 4 's.

A 4-uniform hypergraph represents the P4-structure of a graph G if its hyperedges are the vertex sets of the P4's in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P4-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n2) where n is the number of vertices.

Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of n items on a reconfigurable mesh of size $n \times n$ was running in O(log n ) time. It was open for more than 8 years to obtain a faster algorithm for this important problem. Our main contribution is to provide the first breakthrough: we propose a deterministic list-ranking algorithm that runs in O(log* n ) time as well as a randomized one running in O(1) expected time, both on a reconfigurable mesh of size $n \times n$ . Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes.

In pattern recognition, morphology, and cellular system design one is interested in objects routinely represented by a polygonP. Distance properties among the vertices ofPare one of the fundamental descriptors useful in shape analysis and clustering. In order to capture perceptually relevant features ofPone associates a variety of proximity graphs with the polygonP. Typically such a proximity graphG(P) has the same vertices asP: two vertices ofPare adjacent inG(P) if they satisfy an application-specific predicate.Our main contribution is to propose time-optimal algorithms for constructing the Euclidian minimum spanning tree, the all-nearest neighbor graph, the relative neighborhood graph, and the symmetric farthest neighbor graph of ann-vertex unimodal polygon. All our algorithms run on meshes enhanced with row and column buses. We begin by establishing a ?(logn) time lower bound for the task of computing the Euclidian minimum spanning tree of ann-vertex unimodal polygon. This lower bound holds for both the CREW-PRAM and for meshes with multiple broadcasting, regardless of the number of processors available.Next, we show that this time lower bound is tight by exhibiting an algorithm for the Euclidian minimum spanning tree problem running in ?(logn) time on a mesh with multiple broadcasting of sizen×n. We also show that the all-nearest neighbor graph, the relative neighborhood graph, and the symmetric farthest neighbor graph of ann-vertex unimodal polygon can be computed inO(1) time on a mesh with multiple broadcasting of sizen×n.

The All Nearest Neighbor problem (ANN, for short) is stated as follows: given a setSof points in the plane, determine for every point inS, a point that lies closest to it. The ANN problem is central to VLSI design, computer graphics, pattern recognition, and image processing, among others. In this paper we propose time-optimal algorithms to solve the ANN problem for an arbitrary set of points in the plane and also for the special case where the points are vertices of a convex polygon. Both our algorithms run on meshes with multiple broadcasting. Our first main contribution is to establish an ?(logn) time lower bound for the task of solving an arbitraryn-point instance of the ANN problem, even if the points are the vertices of a convex polygon. We obtain our time lower bound results for the CREW-PRAM by using a novel technique involving geometric constructions. These constructions allow us to reduce the well-known OR problem to each of the geometric problems of interest. We then port these time lower bounds to the mesh with multiple broadcasting using simulation results. Our second main contribution is to show that the time lower bound obtained is tight, by exhibiting algorithms solving the problem inO(logn) time on a mesh with multiple broadcasting of sizen×n.

The main contribution of this work is to present a simple deterministic sampling strategy that, when used for bucket sorting, yields buckets that are remarkably well balanced, making costly balancing unnecessary. To the best of our knowledge, this is the first instance of a deterministic sampling strategy featuring this performance. Although the strategy is perfectly general, we illustrate its power by devising a VLSI-optimal,O(1) time sorting algorithm for the reconfigurable mesh. As a by-product of the inherent simplicity of our sampling and bucketing scheme, we show that our sorting algorithm can be implemented using only 35 broadcast operations, a substantial improvement over the previously best known algorithm that requires 59 broadcasts.

Computing the convex hull of a planar set of points is one of the most extensively investigated topics in computational geometry. Our main contribution is to present the first known general-case, time- and VLSI-optimal, algorithm for convex hull computation on meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, the convex hull of a set of m(n/sup 1/2 + 1/2 c//spl les/m/spl les/n) points in the plane stored in the first [m//spl radic/n] columns of a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n can be computed in /spl Theta/(m//spl radic/n) time. Our algorithm features a very attractive additional property, namely that the time to input the data, the time to compute the convex hull, as well as the time to output the result are essentially the same. >

The P4-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P4-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. A remarkable property of P4-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P4-reducible graphs and to construct their corresponding tree representation.

We present a linear time algorithm for unit interval graph recognition. The algorithm is simple and based on Breadth-First Search. It is also direct — it does not first recognize the graph as an interval graph. Given a graph G, the algorithm produces an ordering of the vertices of the graph whenever G is a unit interval graph. This order corresponds to the order of the intervals of some unit interval model for G when arranged according to the increasing order of their left end coordinates. Breadth-First Search can also be used to construct a unit interval model for a unit interval graph on n vertices; in this model each endpoint is rational, with denominator n.

An independent set { x , y , z } is called an asteroidal triple if between any pair in the triple there exists a path that avoids the neighborhood of the third. A graph is referred to as AT-free if it does not contain an asteroidal triple. We present a simple linear-time algorithm to compute a dominating path in a connected AT-free graph.

Our contribution is twofold. First, we show that Ω(log n ) is a time lower bound on the CREW-PRAM and the mesh with multiple broadcasting for the tasks of computing the perimeter, the area, the diameter, the width, the modality, the smallest-area enclosing rectangle, and the largest-area inscribed triangle of a convex n -gon. We show that the same time lower bound holds for the tasks of detecting whether a convex n -gon lies inside another as well as for computing the maximum distance between two convex n -gons. We obtain our time lower bound results for the CREW-PRAM by using a novel technique involving geometric constructions. These constructions allow us to reduce the well-known OR problem to each of the geometric problems of interest. We then port these time lower bounds to the mesh with multiple broadcasting using simulation results. Our second contribution is to show that the Ω(log n ) time lower bound is tight by providing O (log n ) time algorithms to solve these problems on a mesh with multiple broadcasting of size n × n . Finally, we show that for two separable convex n -gons P and Q , the task of computing the minimum distance between P and Q can be performed in O (1) time on a mesh with multiple broadcasting of size n × n .

The purpose of this paper is to demonstrate that the versatility of the reconfigurable mesh can be exploited to devise constant-time algorithms for a number of important computational tasks relevant to robotics, computer graphics, image processing, and computer vision. In all our algorithms, we assume that one or two n -vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size √ n × √ n . In this setup, we propose constant-time solutions for testing an arbitrary polygon for convexity, solving the point location problem, solving the supporting lines problem, solving the stabbing problem, determining the minimum area/perimeter corner triangle for a convex polygon, determining the k -maximal vertices of a restricted class of convex polygons, constructing the common tangents of two separable convex polygons, deciding whether two convex polygons intersect, answering queries concerning two convex polygons, and computing the smallest distance between the boundaries of two convex polygons. To the best of our knowledge, this is the first time that O (1) time algorithms to solve dense instances of these problems are proposed on reconfigurable meshes.

We consider the following problem. For a binary tree T = ( V , E ) where V = {1, 2, ..., n }, given its inorder traversal and either its preorder or its postorder traversal, reconstruct the binary tree. We present a new parallel algorithm for this problem. Our algorithm requires O ( n ) space. The main idea of our algorithm is to reduce the reconstruction process to merging two sorted sequences. With the best parallel merging algorithms, our algorithm can be implemented in O (log log n ) time using O ( n /log log n ) processors on the CREW PRAM (or in O (log n ) time using O ( n /log n ) processors on the EREW PRAM). Our result provides one more example of a fundamental problem which can be solved by optimal parallel algorithms in O (log log n )time on the CREW PRAM.

Recently, an elegant and powerful architecture called the reconfigurable mesh has been proposed in the literature. In essence, a reconfigurable mesh consists of a mesh-connected architecture enhanced by the addition of a dynamic bus system whose configuration changes in response to computational and communication needs. In this paper we show that the reconfigurable mesh architecture can be exploited to yield very simple constant-time algorithms to solve a number of important computational problems involving trees. Specifically, we address the problem of generating the computation tree form of an arithmetic expression, the problem of reconstructing a binary tree from its preorder and inorder traversals, and the problem of reconstructing an ordered forest from its preorder and postorder traversals. We show that with an input of size n, all these problems find constant-time solutions on a reconfigurable mesh of size n x n. © 1995 Academic Press, Inc.

Up to now, buses have been used exclusively to ferry data around. The contribution of this work is to show that buses can be used both as topological descriptors and as powerful computational devices. We illustrate the power of this paradigm by designing two fast algorithms for image segmentation and parallel visibility. Our algorithm for image segmentation uses a novel technique invol ving building a bus around every region of interest in the image. With a binary image pretiled in the natural way on a reconfigurable mesh of size N×N our segmentation algorithm runs in O( log N) time, improving by a factor of O( log N) over the state of the art. Next, we exhibit a very simple algorithm to solve the parallel visibility problem on an image of size N×N. Our algorithm runs in O( log N) time. The only previously-known algorithm for this problem runs in O( log N) time on a hypercube with N processors. To support these algorithms, a set of basic building blocks are developed which are of independent interest. These include solutions to the following problems on a bus on length N: (1) computing the prefix maxima of items stored by the processors on the bus, even if none of the processors knows its rank on the bus; (2) computing the rank of every processor on the bus; (3) electing a leader on a closed bus.

Given a sorted sequence A = a1, a2, ..., an of items from a totally ordered universe, along with an arbitrary sequence Q = q1, q2, ..., qm (1 ? m ? n) of queries, the multiple search problem involves computing for every qj (1 ? j ? m) the unique ai for which ai?1 ? qj < ai. In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a formula] × formula] mesh with multiple broadcasting, our algorithm runs in formula] time which is shown to be time-optimal. We also present some surprising applications of the multiple search algorithm to computer graphics, image processing, robotics, and computational geometry.

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. The authors show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With a n-vertex cograph G represented by its parse tree as input the algorithm finds a maximum matching in G in O(log n) time using O(n/log n) processors in the EREW-PRAM model. >

Given a sequence of m items α1, α2,…, αm from a semigroup S with an associative operation ⊕, the semigroup computation problem involves computing α1 ⊕ α2 ⊕…⊕ αm. We consider the semigroup computation problem involving m (2≤m≤n) items on a mesh with multiple broadcasting of size [Formula: see text]. Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2≤m≤n). Specifically, we show that any algorithm that solves the semigroup computation problem must take Ω( log m) time if [Formula: see text] and [Formula: see text] time for [Formula: see text]. We then show that our bound is tight by designing an algorithm whose running time matches the lower bound. These results unify and generalize all semigroup lower bounds and algorithms known to the authors.

Data movement operations are central to many efficient algorithms for parallel machines constructed as interconnection networks of processors. The purpose of this work is to present a number of basic data movement techniques for reconfigurable meshes. These include computing the prefix maxima of a sequence of real numbers and computing the prefix sums of a binary sequence. The data movement techniques presented in this paper have far-reaching applications. Among them, we present a new sorting algorithm and an efficient algorithm to find all maximal elements of a planar set of points.

The Parallel Random Access Machine or PRAM model, has been a much employed parallel algorithm development tool for a number of years. As such, many important problems have been solved on this model. Accordingly, considerable attention has been given to the process of simulating PRAM models on more realistic architectures. The purpose of this paper is to present an efficient simulation of the Concurrent Read Exclusive Write PRAM model by the crossbar connected machine (CCM). In addition to simulation, it is proven that all lower bounds for the CREW PRAM directly apply to the CCM. This is the first presentation of algorithmic lower bounds for a crossbar based model. The buses of the network are assumed to have a broadcast delay of δ(n). Recent implementations of the crossbar network in CMOS VLSI technology support the viability of the CCM model. It is the communication flexibility of the crossbar network which supports the PRAM simulations in a very straightforward manner without the complex interconnection systems or high overhead algorithms of many prior simulations.

A graph G is quasi-brittle if every induced subgraph H of G contains a vertex which is incident to no edge extending symmetrically to a chordless path with three edges in either H or its complement H¯. The quasi-brittle graphs turn out to be a natural generalization of the well-known class of brittle graphs. We propose to show that the quasi-brittle graphs are perfectly orderable in the sense of Chvátal: there exists a linear order < on their set of vertices such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c.

The purpose of this paper is to present non-trivial lower bounds for two classes of enhanced meshes. To achieve this goal we present efficient simulations of these two classes of enhanced meshes on the CREW-PRAM and Common-CRCW. From this, known computational lower bounds for the PRAM are transferred to the enhanced meshes. Our approach of transferring lower bounds from the PRAM to enhanced meshes is novel. Specifically, we show that any computation that takes O (t(n)) steps on an n-processor mesh with multiple broadcasting can be performed in O (t(n)) steps on an n-processor CREW-PRAM with O (n) extra memory. Similarly, with α standing for the inverse Ackermann function, we show that any computation that takes O (t(n)) computational steps on an n-processor basic reconfigurable mesh can be performed in O (α(n)t(n)) computational steps on an n-processor Common-CRCW with O (n) extra memory. We also show that some of the lower bounds that we derive are tight by providing matching upper bounds; as an example, we show that n items stored in one row of a mesh with multiple broadcasting can be sorted in O(log n) time and that this is time optimal. The best previously-known algorithm for this problem takes O(log2 n) time.

Many practical problems lend themselves to an integer-based solution. Given such specialized data it is sometimes possible to design algorithms which are more efficient than a corresponding general-purpose algorithm. Integer sorting of the most basic integer-related problems. The purpose of this work is to present applications of reconfigurable meshes to constant time computations involving integers. More specifically, we develop a constant time integer sorting algorithm on a reconfigurable mesh and show how this leads to a constant time parentheses matching algorithm.

We characterize sources in comparability graphs and show that our result provides a unifying look at two recent results about interval graphs.

We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ( log n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.

The purpose of this short note is to show that the problem of reconstructing a directed forest from a collection of leaf-to-root paths can be done efficiently in parallel by reducing the problem to integer sorting. Specifically, given M the total length of the paths in the collection, and n the number of distinct node labels, our algorithm reconstructs the corresponding forest (if such a forest exists) in O(M/p) time using p ≤ M/n processors or [Formula: see text] time using M/n < p < M processors, and O (M) space on the EREW-PRAM.

The problem of computing the lowest common ancestors of all pairs of nodes in a rooted tree is central in a large number of practical applications. The purpose of this note is to propose a very simple cost-optimal parallel algorithm to solve the lowest common ancestor problem. More precisely, with an n-node rooted tree as input, our algorithm runs in O(log n) time using O(n2 lopg n) processors on the EREW-PRAM model.

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper we present two new characterizations of the cographs and show how to use them for the purpose of producing a parallel recognition algorithm for this class of graphs. In addition, if the graph under investigation turns out to be a cograph, our algorithm constructs its corresponding cotree. With an arbitrary graph G with n vertices and m edges as input, the proposed algorithm runs in O(log n) time using O((n2 + mn)/log n) processors on an EREW parallel random access machine.

The measure problem involves computing the area of the union of a set of n iso-oriented rectangles in the plane. Recently, it has been shown that for a set of n such rectangles, the measure problem can be solved in O(log n log log n) time, using O(n/log log n) processors in the CREW PRAM model of computation. In this note we show that the measure problem can be solved optimally in O(log n) time using O(n) processors in the same model of computation, thus settling an open problem posed in [8].

The problem of multiselection arises frequently in databases. Here, given an unordered set S of n records and a sequence of m integers 1 =< q"1 < q"2 < ... < q"m =< n we are interested in answering queries of the type 'find the q"ith smallest elements in S', the problem is to answer all these queries as fast as possible. We propose an efficient parallel algorithm for multiselection, running in O(n/p log 2m) time using p processors with 1 =< p =< [n/log n log* n], in the EREW-PRAM model.

Quite recently it has been proved that a two-dimensional processor array with a reconfigurable bus system (PARBS, for short) is at least as powerful as the CRCW shared memory computer. In this note we argue that the well-known PARITY problem can be solved in O(1) time on a two-dimensional PARBS of (n+1)×n processors. Since it is known that PARITY cannot be solved in constant time on a CRCW even if a polynomial number of processors is available, our result shows that the two-dimensional PARBS is strictly more powerful than the CRCW.

We characterize interval graphs in terms of a certain linear order on their vertex set. It turns out that with this linear order, the well-known greedy heuristic “always use the smallest available color” yields an exact coloring algorithm for interval graphs. In addition, the heuristic can be implemented to run in linear time.

We define a class of graphs which generalizes the well-known class of cographs or complement-reducible graphs and show that the graphs in our class can be recognized fast in parallel. More precisely, with an arbitrary graph G with n vertices and m edges as input, the proposed recognition algorithm runs in O(log n ) time using O(( n 2 /log n )+ mn ) processors on an EREW parallel random access machine.