The creation of context-aware services in pervasive computing environments has driven the wide development of wireless local area network (WLAN)-based indoor positioning systems. One of the main challenges in WLAN-based indoor positioning is the severe fluctuation of received signal strength (RSS), which may cause the RSS patterns to be mismatched and the positioning to be inaccurate. In this paper, an indoor positioning algorithm that combines the fingerprint scheme with mobility prediction is proposed. Since the mobility prediction is performed according to the moving speed and direction of the mobile client, the resulting location estimation is more stable compared to the use of RSS alone. Experimental results show that the proposed positioning algorithm can mitigate the impact of the RSS fluctuation and has better positioning accuracy and stability than previous fingerprint-based approaches.

Network coding is a promising technology proven to improve the performance of wireless networks. To successfully design a quality-of-service (QoS)-satisfied routing protocol with network coding, the bandwidth consumption of a coding host should be determined. Furthermore, coding opportunities should be increased to improve network capacity. Nevertheless, it is challenging to determine whether a host can be a coding host and to determine the bandwidth consumption of a coding host in a mobile ad hoc network (MANET). In this paper, we first present and define the coding conditions to identify a coding host. The bandwidth consumption of a coding host is then estimated under the contention-based wireless networks with a random access mechanism. Finally, we propose a bandwidth-satisfied and coding-aware multicast routing protocol (BCMRP). By taking into account the residual bandwidth of the carrier-sense neighbors of the forwarders, the proposed protocol can satisfy the bandwidth requirements of the requested flow and other ongoing flows. As a consequence of considering coding opportunities in multicast tree construction, the proposed multicast protocol can reduce the total bandwidth consumption. The simulation results show that BCMRP outperforms the prior multicast routing protocols in receiving ratio, admission ratio, and total bandwidth consumption.

In recent years, wireless network structures and mechanisms have been proposed to enhance the efficiency of communications. Regarding the upper-layer of protocol stacks, wireless transmission control protocols (WTCPs) are proposed to deal with transmission control protocol (TCP) performance problems on wireless networks. However, some new lower-layer solutions, e.g., cognitive radio (CR) systems, cause new throughput decay problems to TCPs, which existing WTCPs do not solve. In this paper, we study throughput decay issues in CR environments and discuss three events that cause these problems. Three event handlers are proposed to improve TCP throughput. The proposed solutions are designed by numerical analysis, and performance improvement is verified by NS2. We propose an event-driven CR-TCP that combines these event handlers, which can be combined with state-of-art CR-TCP solutions. Simulation results and analysis are presented to demonstrate the effectiveness of the proposed solution.

Range-free localization approaches are cost-effective for mobile sensor networks (because no additional hardware support is required). However, existing range-free localization approaches for mobile sensor networks suffer from either sparse anchor node problem or high communication cost. Due to economic considerations, mobile sensor networks typically have sparse anchor nodes which makes most range-free localization algorithms inaccurate. On the other hand, due to the power limitation of mobile sensor nodes (i.e., they are battery-operated) and high power consumption by communication, high communication cost will significantly reduce the network life time. For solving these two problems, in this paper, we use historical beacons (i.e., anchor nodes' announcements delivered in previous time slots) and received signal strength (RSS) to derive three constraints. By the aid of the three constraints, we introduce a low-communication-cost range-free localization algorithm (only one-hop beacon broadcasting is required). According to the theoretical analysis and simulation results, our three constraints can indeed improve the accuracy. Simulation results also show that our algorithm outperforms even in irregular-radio-signal environments. In addition, a hardware implementation running on sensor nodes, Octopus Xs, confirms theoretical analysis and simulation results.

The fingerprint-based techniques are commonly used for indoor location estimation, in which a radio map is built by calibrating signal-strength values at several training locations in the offline phase. However, the signal-strength values change as the environment changes, and hence the radio map built may be out of date. Further, the recalibration of signal-strength values for each environment change is laborious and time consuming. Therefore, in this paper, an efficient radio map management method is proposed in response to the environment changes. We first demonstrate that different features of signal propagation are obtained in different regions of the indoor environment. According to the different features of signal propagation, the environment is divided into several regions and the signal-strength values collected at the training locations in different regions can be updated accurately and individually using proper propagation features. The experimental results show the usefulness of the proposed method and the accuracy of the localization can be improved.

In this paper, based on the concept of ceased areas, the spatial reuse in IEEE 802.11 ad hoc networks is enhanced by transmission power control (TPC). A ceased area is created by a transmitter-receiver pair where all other nodes should cease their transmissions for a while. The size of a ceased area varies with the transmission power. A new TPC scheme that can minimize the induced ceased area is proposed. It is practical without needs to know the transmitter-receiver distance. And its performance in network throughput is superior to previous TPC schemes.

Abstract Suppose G is a connected graph and T a spanning tree of G. A vertex v ε V(G) is said to be a degree‐preserving vertex if its degree in T is the same as its degree in G. The degree‐preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree‐preserving vertices is maximized. The purpose of this article is to provide an O(m.α(m,n))‐time algorithm for the degree‐preserving spanning tree problem in strongly chordal graphs, where α is the inverse of Ackermann's function. Furthermore, we present an O(m + n)‐time algorithm in directed path graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Since the multi-rate enhancements have been implemented in wireless ad hoc networks (MANETs), QoS-constrained multicast protocols for multimedia communication should be adapted to exploit them fully for using more efficiently the limited resources. To build a multicast tree with delay-guaranteed, one-hop delay and end-to-end delay must be known. The one-hop delay is the transmission time at a given link connecting two neighboring hosts, and the end-to-end delay is the time taken for a data packet from a specific source to reach the destination node. However, how to calculate the above two delays using the IEEE 802.11 MAC is still a challenging problem, because the radio channel is shared among neighbors. Further, the multi-rate enhancements make it more difficult since the neighboring relation among hosts is varied with the transmission rates. In this paper, we first propose a method to estimate the one-hop delay based on varied transmission rates by monitoring the sensed busy/idle ratio of shared channel. Then, by its aid, another method is proposed to compute the end-to-end delay. Finally, we integrate the above two methods with a typical multicast routing protocol, ODMRP, for constructing a delay-guaranteed multicast protocol. Simulation results show that the proposed method obtains more precise one-hop delay than a very recently work. Besides, the integrated protocol provides better delay guarantee than the existing protocol when the multicast traffic has delay requirement.

Event detection and environment surveillance are the important issues in wireless sensor networks. However,using the non-renewable power source leads to the short lifetime of the networks. For this reason the scheduling process is to determine the time sensor node wakes up and goes sleeping to conserve energy, so the delay time and the working interval would become trade-off. In this article, we introduce the two ranked aware phase surveillance to lower the delay time, and we use the sensed data to make the scheduling policy.We consider the event happening in two phase, so we propose two surveillance models to cope with these two phases,although this model is simple to create it can achieve the goal of reducing the delay time of detection and delivery. Finally, we show our performance in the simulation section and then describe the improvement of our approach in the future work section.

Abstract The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Previously, the alternating group graph was shown to be pancyclic, i.e., containing cycles of all possible lengths. In this article, we further show that the alternating group graph remains pancyclic, even if there are up to 2n − 6 edge faults, where n ≥ 3 is the dimension of the alternating group graph. The result is optimal with respect to the number of edge faults tolerated. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

In last decades, the demand of wireless spectrum has increased rapidly with the development of mobile communication services. Recent studies recognize that traditional fixed spectrum assignment does not use spectrum efficiently. Such a wasting phenomenon could be amended after the present of cognitive radio. Cognitive radio is a new type of technology that enables secondary usage to unlicensed user. This paper presents an opportunistic cognitive MAC protocol (OC-MAC) for cognitive radios to access unoccupied resource opportunistically and coexist with wireless local area network (WLAN). By a primary traffic predication model and transmission etiquette, OC-MAC avoids producing fatal damage to licensed users. Then a ns2 simulation model is developed to evaluate its performance in scenarios with coexisting WLAN and cognitive network.

Abstract The w‐Rabin number of a network W is the minimum l so that for any w + 1 distinct nodes s, d1,d2,…,dw of W, there exist w node‐disjoint paths from s to d1,d2,…,dw, respectively, whose maximal length is not greater than l, where w is not greater than the node connectivity of W. If {d1,d2,…,dw} is allowed to be a multiset, then the resulting minimum l is called the strong w‐Rabin number of W. In this article, we show that both the w‐Rabin number and the strong w‐Rabin number of a k‐dimensional folded hypercube are equal to ⌈k/2⌉ for 1 ≤ w ≤ ⌈k/2⌉‐ 1, and ⌈k/2⌉+ 1 for ⌈k/2⌉ ≤ w ≤ k + 1, where k ≥ 5. Each path obtained is shortest or second shortest. The results of this paper also solve an open problem raised by Liaw and Chang. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Previous quality-of-service (QoS) routing/multicasting protocols in mobile ad hoc networks determined bandwidth-satisfied routes for QoS applications. However, they suffer from two bandwidth-violation problems, namely, the hidden route problem (HRP) and the hidden multicast route problem (HMRP). HRP may arise when a new flow is permitted and only the bandwidth consumption of the hosts in the neighborhood of the route is computed. Similarly, HMRP may arise when multiple flows are permitted concurrently. Not considering the bandwidth consumption of two-hop neighbors is the reason that the two problems are introduced. In this paper, a novel algorithm that can avoid the two problems is proposed to construct bandwidth-satisfied multicast trees for QoS applications. Furthermore, it also aims at minimizing the number of forwarders so as to reduce bandwidth and power consumption. Simulation results show that the proposed algorithm can improve the network throughput.

This paper presents an online measurement-based admission control scheme on the basis that the aggregate VBR video traffic is lognormally distributed. The proposed scheme consists of two components: measurement process and admission decision. The measurement process applies a linear Kalman filter to estimate statistical parameters of aggregate VBR video traffic. The estimated statistical parameters are used to calculate the effective bandwidth for admission decision. Variable bit rate (VBR) video traffic with high data rate is expected to occupy a dominant proportion of bandwidth for future wireless broadband home networks. To guarantee quality-of-service (QoS) of such VBR video streams, while achieving a high level of channel utilization, an efficient admission control scheme is urgently required, especially for emerging wireless multimedia indoor services, such as HDTV, online video game, etc. The proposed scheme is computationally efficient and accurate without much prior traffic information. Simulation results verify its effectiveness and show that it performs well for both a small number of connections and a large number of connections.

The bandwidth-constrained routing problem (BCRP) asks for a route that has sufficient bandwidth for data transmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it is defined for wireless ad hoc networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMA-based. In this paper, we show that BCRP is still NP-complete, even if CSMA-based or contention-based CDMA MAC prot.ocols are used. Besides, we show that BCRP is polynomial-time solvable if the channel model is collision-free and the scheduling policy is FIFO. In wireless ad hoc networks, no MAC protocol was designed before, which would lead to a polynomial-time solution to BCRP. The results of this paper suggest a design for MAC protocols that can support QoS routing well.

In this paper, we design a novel transmission structure called a double-tree for correlated data gathering problem for wireless sensor networks, where the goal is to minimize the total transmission cost of information collected by all sensor nodes, to the sink node. It is well-known that a tree structure is often adopted for network routing problems. However, the traditional tree transmission structure for network routing may not be an optimal structure while data correlation factors are being considered. For a given wireless sensor network, some nodes send their raw data directly to the sink, and some nodes send their encoded data based on information received from other nodes; therefore, there are two types of data in the network. Without the help of decoding/re-coding at the intermediate node, the purpose of encoded data routing is to directly send to the sink, but the purpose of raw data routing is not only to send to the sink, but also to spread raw data to other nodes as side information in encoding operations. The difference from one data type makes traditional tree structure unsuitable for the correlated data gathering problem. Therefore according to our observations, we propose a new transmission double-tree structure, which uses one tree for raw data routing, and uses another tree for encoded data routing. By employing the double-tree structure, the network can achieve lower transmission cost of gathering sensing data. Furthermore the adoption of double-tree structure always outperforms the traditional tree structure in correlated data gathering problem. We first formulate the optimization problem with a double-tree transmission structure in the general case, and prove NP-Hardness of simplified version of this problem. Then we present a 2-approximation algorithm MST+SPT that guarantees the upper bound of total transmission cost compared to the optimal solution.

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced (or repaired) in each iteration provided there are at most t faulty processors, where $t \ge k$. This paper suggests lower bounds on the degrees of $(t,k)$-diagnosability of multiprocessor systems under both the PMC and the MM* models. As a consequence, grids and tori of d dimensions are shown to be $(\Omega(N^\frac{d}{d+1})$, $\Omega(d))$-diagnosable and $(\Omega(N^\frac{d}{d+1})$, $\Omega(2d))$-diagnosable, respectively, where N is the number of processors.

IEEE 802.15.3, an emerging wireless technology, was designed to provide high-quality multimedia services at home. Dynamic bandwidth allocation for a multimedia connection should be considered in order to achieve higher channel utilization, less buffer and less delay, especially for variable bit rate (VBR) multimedia connections. For real-time VBR videos, the bandwidth requirement should be predicted adaptively for effective channel-time requests. Previously, the adaptive least-mean square (LMS) algorithm with fixed step size was applied to predict channel time requirements due to its simplicity and relatively good performance. However, the performance might degrade when scene changes occurred. In this paper, we modify the variable step-size LMS algorithm and apply it as our predictor (VSSNLMS) so that the prediction errors on scene changes can be effectively reduced. Using the prediction results of VSSNLMS, we propose a dynamic bandwidth-allocation scheme that is scene-change aware and can guarantee the delay bound of real-time VBR videos. Simulation results show that the VSSNLMS predictor is superior to previous LMS-type predictors in performance, and the proposed scheme has better performance in channel utilization, buffer usage, and packet loss

The hierarchical hypercube network is suitable for massively parallel systems. An appealing property of this network is the low number of connections per processor which can facilitate the VLSI design and fabrication of the system. Other alluring features include symmetry and logarithmic diameter, which imply easy and fast algorithms for communication. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of the hierarchical hypercube network. Their maximal length is not greater than max{2/sup m+1/ + 2m + 1, 2/sup m+1/ + m + 4},where 2/sup m+1/ is the diameter.

The Bandwidth-Constrained Routing Problem (BCRP) asks for a route that has sufficient bandwidth for data transmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it is defined for multi-hop wireless networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMA-based. In this paper, we show that BCRP is still NP-complete, even if CSMA-based or contention-based CDMA MAC protocols are used. Besides, we show that BCRP is polynomial-time solvable if the underlying MAC protocol adopts CDMA channel model and FIFO scheduling policy. In multi-hop wireless networks, no MAC protocol was designed before which would lead to a polynomial-time solution to BCRP. The results of this paper suggest a design principle for MAC protocols that can support QoS routing well.

A new diagnosis strategy called c-step diagnosis is proposed. A system is c-step t-diagnosable if all faulty units within the system can be identified and repaired in at most c iterations provided the number of faulty units present does not exceed t. The upper bound and the lower bound on the c-step diagnosabilities were derived. Moreover, an upper bound on c was suggested

The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube can tolerate up to 2n - 5 link faults, while retaining a fault-free Hamiltonian cycle. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its probability to occur, which is very close to 1, even if n is small

Recently, ultra-wideband (UWB) technologies have attracted considerable attention for its capability, high data rate to achieve 480 Mbps, to wireless personal communications. In this paper, the problem of TCP and energy efficient transmission in IEEE 802.15.3 WPAN based on UWB technologies are addressed. Also, a simple power-efficient scheme for TCP transmission in accordance with IEEE 802.15.3 WPAN standard is proposed and NS2 is used for evaluating the performance of this proposal. The scheme design is driven by two major factors. The first one is that the scheme should provide high TCP throughput in a piconet and low end-to-end delay for TCP packets. The second one is that the scheme should be energy efficient since most mobile devices typically are powered by battery and have limited power capacity. In order to meet these requirements, the energy efficient design at the MAC layer and transport layer is taken into account by the proposed schema

With the wireless technology development, more and more standards are declared for certain purpose and many of them have to share the same radio frequency spectrum. On the other hand,because many requests from unstable traffic use the peak rate and some behavior of bursted traffic, the utilization of the channel might be low in most of the time. Therefore, the radio frequency spectra are treasurable and issues about increasing or balancing spectrum utilization become more important. CR (cognitive radio) technique is now developing for solving this critical problem. CR technique includes many aspects of researches, such as reusing spectrum holes invisibly, learning form users' behavior, adjusting changes form the environment automatically, and so on. This paper gives out a cognitive borrowing algorithm which can ensure the QoS of primary users. By using this algorithm with environment scanning capability, CR traffics raise the utilization of the channel with only rare damage to prior users. Moreover, the algorithm has the advantages of decentralized system, flexibility, low computing complexity, and fairness

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t /spl ges/k This paper proposes a (t,k) diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that matching composition networks of n dimensions are (/spl Omega/(2/sup n//spl middot/logn/n),n)-diagnosable, where n > 5.

Due to varying wireless channel conditions, the IEEE 802.11 wireless local area network (WLAN) standard supports multiple modulation types to accommodate the tradeoff between data rate and bit error rate. In Heusse(2003), Rousseau, Berger-Sabbatel and Duda theoretically analyzed a performance anomaly when multi-rate stations with different modulation types exist in IEEE 802.11 WLANs. The performance anomaly is: the aggregate throughput of those stations transmitting at a higher data rate will dramatically degrade below the same level as that of those stations transmitting at a lower data rate. In this paper, we address the anomaly problem and formulate a nonlinear mixed integer programming problem to maximize the total aggregate throughput of all stations subject to that the channel occupancy times among the stations transmitting at different data rates are kept at a fairness ratio. With its aid, a single-hop WLAN can dynamically accommodate the resource access usage to maximize the system throughput in varying fading environments. We prove that the optimization problem is intractable and propose a heuristic solution based on a penalty function with gradient-based approach to solve it. We show the effectiveness of the approach via computational experiments and provide some useful guidelines to regulate the parameters needed for the approach.

In this paper, we propose U-MAC, a medium access control protocol designed for wireless sensor networks. Nowadays, wireless sensor network are formed by a great quantity of sensor nodes, which are generally battery-powered and may not recharge easily. Consequently, how to prolong the lifetime of the nodes is an important issue while designing a MAC protocol. However, lowering the energy consumption may result in higher latency. Addressing on such tradeoff, U-MAC balances the tradeoff by utilization based tuning of duty cycle and selective sleeping after transmission. The experiment results show that our proposed U-MAC saves energy about 43% and reduce latency by 65% from S-MAC in a chain topology. In the cross topology, U-MAC also achieves 32% energy saving and 45% latency reduction from S-MAC.

In the existing mobile ad hoc network (MANET) QoS routing and multicasting protocols, the methods of bandwidth calculation and allocation were proposed to determine routes with bandwidth guaranteed for QoS applications. As our observations, two bandwidth-violation problems is incurred in the above protocols. First: When a new bandwidth-requirement flow starts, the existing methods determine a bandwidth-satisfied route and reserve the bandwidth for the flow accordingly by considering the nodes' status on the route and network configuration. However, the reservation might violate the bandwidth capacities of other ongoing bandwidth-consuming flows. Second: Another bandwidth-violation problem would mislead the bandwidth reservation for QoS multicast applications when the multiple routes from a server to all clients were determined concurrently. Our simulation results exhibit that the two problems have high possibilities to be incurred so as to cause serious performance declination while the network traffic is heavy. In this paper, the problem of determining a bandwidth-satisfied tree is formulated as a 0/1 integer linear programming (ILP) for the theoretical studies. We minimize the number of forwarders for reducing the number of hosts participating in packet forwarding so as to lower bandwidth and power consumption that are crucial to MANET performance.

In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. and the pessimistic diagnosis strategy proposed by Friedman. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others.

Broadcast/multicast is a key service for mobile ad hoc networks. A great number of applications rely on a reliable and efficient MAC layer broadcast. The IEEE 802.11 broadcast protocol, which is based on carrier sense multiple access with collision avoidance (CSMA/CA), does not offer any MAC layer recovery on broadcast frames. Consequently, the increasing probability of lost frames may deteriorate the quality of broadcast/multicast services offered at upper layers. In this paper, we first formulate the broadcast problem as an optimization problem and show that it is NP-hard, even if the upper layer service is periodical beacons. An approximation algorithm with a guaranteed approximation ratio is also suggested. Then, a reliable and efficient MAC layer broadcast protocol, named broadcast protocol with busy tone (BPBT), is proposed. BPBT applies a busy tone to solve the hidden terminal problem. Finally, BPBT is compared with previous protocols for performance evaluation by simulation.

The IEEE 802.11 working group has been developing a new distributed MAC, called the enhanced distributed function (EDCF), to support service differentiation in the IEEE 802.11 MAC protocol. Besides, highspeed WLAN environments are also expected to provide wireless Internet services in hot spots such as airports, parks, etc. Since there are usually multiple service providers competing for providing wireless network access in hot spots, mobile users are free to choose their own service providers. In this paper, we analyze the resource management problem in the competitive environment, in which the EDCF protocol is implemented in all access points (APs) and mobile stations. We formulate admission control as a game and prove the game owns a Nash equilibrium solution. Based on the game, a service provider not only fulfills, for the most part, the QoS satisfaction of ongoing flows but also increases its own revenue. We evaluate the performance by means of throughput, packet delay and bandwidth violation ratio.

Abstract A hierarchical cubic network was proposed as an alternative to the hypercube. By HCN(n), we denote the hierarchical cubic network that contains 2nn‐dimensional hypercubes. In this paper, using Gray codes, we construct fault‐free Hamiltonian cycles in an HCN(n) withn− 1 link faults. Since the HCN(n) is regular of degreen+ 1, the result is optimal. We also construct longest fault‐free cycles of length 22n− 1 in an HCN(n) with a one‐node fault and fault‐free cycles of length at least 22n− 2fin an HCN(n) withf‐node faults, where 22nis the number of nodes in the HCN(n),f≤n− 1 ifn= 3 or 4 andf≤nifn≥ 5. Our results can be applied to the hierarchical folded‐hypercube network as well. © 2003 Wiley Periodicals, Inc.

With the provisioning of high-speed wireless LAN (WLAN) environments, traffic classes (e.g., VoIP or video-conference) with different QoS requirements will be introduced in future WLANs. The IEEE 802.11e draft is currently standardizing a distributed access approach, called the enhanced distributed coordination function (EDCF), to support service differentiation in the MAC layer. However, since each mobile station transmits data packets egotistically in a distributed environment, the QoS requirement of each traffic class may not be guaranteed. In this paper, we develop an admission control strategy to guarantee the QoS requirement of each traffic class. In order to provide a criterion for admission decision, we introduce an analytical model for EDCF to evaluate the expected bandwidth and the expected packet delay of each traffic class. The admission control strategy uses the performance measures derived from the analytical model to decide if a new traffic stream is permitted into the system. We validate the accuracy of the analytical model by using the ns-2 simulator. Some performance evaluations are also demonstrated to illustrate the effect of the proposed admission control strategy.

Recent routing protocols and multicast protocols in ad-hoc networks adopt two-tier architecture to accommodate the effectiveness of the flooding scheme and the efficiency of the tree-based scheme. Some hosts with maximum neighbor degree are chosen as RPs (rendezvous point) to forward data. However, these hosts will higher possibility to be the traffic concentration and bottleneck of the network, and RPs will spend more time forwarding data due to maximum neighbor degree. In this paper, we propose a multicast protocol for ad-hoc network, called OGHAM, with shorter relay and less concentration via selecting RPs from the hosts with minimum hop distance between them and from other normal hosts to these selected RPs rather than the hosts with maximum neighbor degree.

Abstract An ad hoc network is formed by a collection of mobile nodes without any centralized access point or existing infrastructure. Communications between mobile nodes require routing over multiple‐hop wireless paths. Since mobile nodes could be of high mobility, an effective and adaptive routing protocol must have ongoing details of the topology information. However, it wastes limited bandwidth to keep routing information up‐to‐date and reliable. Thus, one of the crucial design objectives to achieve routing responsiveness and updating efficiency is the minimization of reaction to mobility. Specifically, a scalable and QoS‐guaranteed routing protocol is desired for novel multimedia applications in mobile ad hoc networks. In this paper, we propose an efficiently repairable routing protocol, called Gravitational Cluster Routing (GCR) Protocol. It contains a stable cluster structure to cover dense areas and avoid articulation nodes. The reaction to mobility can be reduced significantly by unicast. Active routing paths can be maintained locally in each cluster. Besides, repairable levels of active routing paths, which rank their stabilities, are evaluated. By their aid, the proposed GCR can find routing paths that satisfy different parameters of QoS. These mechanisms can improve the stability of active connections. Copyright © 2003 John Wiley & Sons, Ltd.

An ad-hoc network is formed by a collection of mobile nodes without any centralized access point or existing infrastructure. Communication between mobile nodes requires routing over the multiple-hop wireless path. Since the mobile nodes could be of high mobility, the effective and adaptive routing protocol must have on-going detail of the topology information. However, it wastes limited bandwidth to keep routing information up-to-date and reliable. Thus, a crucial algorithm design objective to achieve routing responsiveness and updating efficiency is the minimization of reaction to mobility. This paper proposes an efficiently repairable routing protocol, called as gravitational cluster routing (GCR) protocol. It is based on a stable cluster structure that covers dense areas to increase stability, and avoids articulate nodes in the cluster to connect strongly and adopts unicast to minimize reaction to mobility. The active routing paths of GCR can be maintained locally by individual stable clusters and globally by quantifying the corresponding repairable levels to satisfy the distinct demand parameters of QoS. These mechanisms improve the stability of active connections.

Abstract Ann‐dimensional hierarchical cubic network [denoted by HCN(n)] contains 2nn‐dimensional hypercubes. The diameter of the HCN(n), which is equal ton+ ⌊(n+ 1)/3⌋ + 1, is about two‐thirds the diameter of a comparable hypercube, even though it uses about half as many links per node. In this paper, a maximal number of node‐disjoint paths are constructed between every two distinct nodes of the HCN(n). Their maximal length is bounded above byn+ ⌊n/3⌋ + 4, which is nearly optimal. The (n+ 1)‐wide diameter andn‐fault diameter of the HCN(n) are shown to ben+ ⌊n/3⌋ + 3 orn+ ⌊n/3⌋ + 4, which are about two‐thirds those of a comparable hypercube. Our results reveal that the HCN(n) has a smaller wide diameter and fault diameter than those of a comparable hypercube. © 2002 Wiley Periodicals, Inc.

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let T d |V|,|E|) and P d (|V|,|E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M d . Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V|+|E|) time, and solved in parallel in O(T d (|V|,|E|)+log |V|) time using O(P d (|V|,|E|)+|V|log |V|)processors on M d . By constructing a decomposition tree under a CREW PRAM, we also show that T d (|V|,|E|)=O(log 2 |V|) and P d (|V|,|E|)=O(|V|+|E|).

Routing functions have been shown effective in deriving disjoint paths in the hypercube. In this paper, using a minimal routing function, k+1 disjoint paths from one node to another k+1 distinct nodes are constructed in a k-dimensional folded hypercube whose maximal length is not greater than the diameter plus one, which is minimum in the worst case. For the general case, the maximal length is nearly optimal (/spl les/ the maximal distance between the two end nodes of these k+1 paths plus two). As a by-product, the Rabin number of the folded hypercube is obtained, which is an open problem raised by S.C. Liaw and G.J. Chang (1999).

An n-dimensional hierarchical cubic network (denoted by HCN(n)) contains 2/sup n/ n-dimensional hypercubes. The diameter of an HCN(n), which is equal to n+[(n+1)/3]+1, is about two-thirds the diameter of a comparable hypercube, although it uses about half as many links per node. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of an HCN(n). Their maximal length has an upper bound of n+[n/3]+4, which is nearly optimal. The (n+1)-wide diameter and n-fault diameter of an HCN(n) are shown to be n+[n/3]+3 or n+[n/3]+4, which are about two-thirds those of a comparable hypercube. Our results reveal that an HCN(n) has shorter node-disjoint paths, wide diameter, and fault diameter than a comparable hypercube.

Abstract Given a connected graphG, a spanning subgraphG′ofGis called at‐spanner if every pair of two adjacent vertices inGhas a distance of at mosttinG′. At‐spanner of a graphGis minimum if it contains minimum number of edges among allt‐spanners ofG. Finding minimum spanners for general graphs is rather difficult. Most of previous results were obtained for some particular graphs, for example, butterfly graphs, cube‐connected cycles, de Bruijn graphs, Kautz graphs, complete bipartite graphs, and permutation graphs. The butterfly graphs were originally introduced as the underlying graphs of FFT networks which can perform the fast Fourier transform (FFT) very efficiently. In this paper, we successfully construct most of the minimumt‐spanners for thek‐aryr‐dimensional butterfly graphs for 2 ≤t≤ 6 andt= 8. © 2001 John Wiley & Sons, Inc.

The arrangement graph is a generalization of the star graph. Recent work by Hsieh et al. showed that an arrangement graph with faulty vertices contains a longest fault-free cycle. In this paper, we generalize Hsieh et al.'s result by constructing a longest fault-free path between two arbitrary distinct healthy vertices. Moreover, our result can tolerate more faulty vertices than can Hsieh et al.'s result. The situation of simultaneous faulty vertices and faulty edges is also discussed. © 2001 John Wiley & Sons, Inc.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

In this paper, we aim to embed longest fault-free paths in an n-dimensional star graph with edge faults. When n/spl ges/6 and there are n-3 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices, exclusive of two exceptions in which at most two vertices are excluded. Since the star graph is regular of degree n-1, n-3 (edge faults) is maximal in the worst case. When n/spl ges/6 and there are n-4 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices. The situation of n<6 is also discussed.

The arrangement graph, denoted by A/sub n,k/, is a generalization of the star graph. A recent work by S.Y. Hsieh et al. (1999) showed that when n-k/spl ges/4 and k=2 or n-k/spl ges/4+[k/2] and k/spl ges/3, A/sub n,k/ with k(n-k)-2 random edge faults, can embed a Hamiltonian cycle. In this paper, we generalize Hsieh et al. work by embedding a Hamiltonian path between arbitrary two distinct vertices of the same A/sub n,k/. To overcome the difficulty arising from random selection of the two end vertices, a new embedding method, based on a backtracking technique, is proposed. Our results can tolerate more edge faults than Hsieh et al. results as k/spl ges/7 and 7/spl les/n-k/spl les/3+[k/2], although embedding a Hamiltonian path between arbitrary two distinct vertices is more difficult than embedding a Hamiltonian cycle.

Butterfly graphs were originally defined as the underlying graphs of fast Fourier transform (FFT) networks, which can perform the FFT very efficiently. Since butterfly graphs are regular, of degree four, they can tolerate at most two edge faults in the worst case in order to establish a Hamiltonian cycle. In this paper, we show that a butterfly graph contains a fault-free Hamiltonian cycle even if it has two random edge faults.

This paper introduces a pancyclic recursive topology, named the hypercomplete, for building large-scale distributed multicomputer systems. The hypercomplete is maximally fault-tolerant and has a logarithmic diameter. In addition to being pancyclic, the hypercomplete is Hamiltonian-connected. Consequently, the hypercomplete can embed rings of all possible lengths and a longest linear array between arbitrary two nodes. Besides, the hypercomplete can embed tori and trees with constant dilation and constant congestion. Some algorithms are developed for the hypercomplete. An algorithm is proposed to determine a shortest path between arbitrary two nodes. A broadcasting algorithm without redundant messages is proposed, whose resulting spanning tree has its height bounded above by the diameter. The class of ascend/descend algorithms can be executed efficiently. © 2000 John Wiley & Sons, Inc.

Suppose that G is a bipartite graph with its partite sets of equal size. G is said to be strongly Hamiltonian-laceable if there is a Hamiltonian path between every two vertices that belong to different partite sets and there is a path of (maximal) length N - 2 between every two vertices that belong to the same partite set, where N is the order of G. In other words, a strongly Hamiltonian-laceable graph has a longest path between every two of its vertices. In this paper, we show that the star graphs with dimension four or larger are strongly Hamiltonian-laceable. © 2000 john Wiley & Sons, Inc.

Three problems in connection with cycles on the butterfly graphs are studied in this paper. The first problem is to construct complete uniform cycle partitions for the butterfly graphs. Suppose that G = (V, E) is a graph. A partition {V1, V2, …, Vs} of V is said to be a uniform cycle partition of G if |V1| = |V2| = … = |Vs| and each subgraph of G induced by Vi contains a cycle of length |Vi|, where 1 ≤ i ≤ s. We say that G has λ-complete uniform cycle partitions if G has uniform cycle partitions whose cycle lengths include all possible multiples of λ. The second problem is to determine if there exists a cycle of length n in the butterfly graphs, where n is arbitrarily given. The third problem is to establish Hamiltonian cycles in faulty butterfly graphs. The results of this paper reveal that the butterfly graphs are superior in embedding rings. © 2000 John Wiley & Sons, Inc.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

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/.

The purpose of the paper is to investigate combinatorial properties of the hypernet network. The hypernet network owns two structural advantages: expansibility and equal degree. In addition, it was shown to be efficient in both communication and computation. Since the number of nodes contained in the hypernet network increases very rapidly with expansion level, we emphasize the hypernet network of two levels (denoted by HN(d, 2)) with a practical view. Recently, combinatorial properties such as container (i.e., node-disjoint paths), wide diameter, and fault diameter have received much attention due to their increasing importance and applications in networks. The following results are obtained for HN(d, 2): (1) best containers with width d-1, (2) containers with (maximum) width d, (3) the (d-1)-wide diameter, (4) the d-wide diameter, (5) the (d-2)-fault diameter, and (6) the (d-1)-fault diameter. More specifically, between every two nodes of HN(d, 2), d (or d-1) packets can be transmitted simultaneously with at most D+2 (or D+1) parallel steps, where D=2d+1 is the diameter of HN(d, 2). Besides, the diameter of HN(d, 2) will increase by at most two (or one), if there are at most d-1 (or d-2) node faults. Our results reveal that HN(d, 2) is not only efficient in parallel transmission, but robust in fault tolerance.

A recursive network can be constructed with basic building blocks in a recursive manner. For example the hypercube is a recursive network because an n-dimensional hypercube consists of two (n-1)-dimensional hypercubes. A recursive network is said to be with complete connection if the subnetwork that constitute it are connected as a complete graph. A general broadcasting scheme is proposed for recursive networks with complete connection. The scheme is simple, efficient, and easy to be implemented. Moreover, no redundant message will be generated. Four networks: WK-recursive networks, hypercomplete networks, hypernet networks, and star networks, are taken as examples to show the effectiveness of the scheme.

The cycle partition problem and the pancycle problem on butterfly graphs are studied in this paper. Suppose G=(V,E) is a graph and {V/sub 1/,V/sub 2/,...,V/sub s/} is a partition of V. We say that {V/sub 1/,V/sub 2/,...,V/sub s/} forms a cycle partition of G if each subgraph of G induced by V/sub 1/ contains a cycle of length |V/sub i/|, where 1/spl les/i/spl les/s. A cycle partition {V/sub 1/,V/sub 2/,...,V/sub s/} is /spl lambda/-uniform if |V/sub 1/|=|V/sub 2/|=...=|V/sub s/|=/spl lambda/. G has /spl lambda/-complete uniform cycle partitions if G has m/spl lambda/-uniform cycle partitions for all 1/spl les/m/spl les/(r+n)/2 and m dividing |V|//spl lambda/. Let BF(k,r) denote the r-dimensional k-ary butterfly graph. For the cycle partition problem, we construct a lot of uniform cycle partitions for BF(k,r). Besides, we construct r-complete uniform cycle partitions for BF(2,r), and kr-complete uniform cycle partitions for BF(k,r). For the pancycle problem, given any pair of n and r we can determine if there exists a cycle of length n in BF(2,r), and construct it if it exists. The results of this paper reveal that the butterfly graphs are superior in embedding rings. They can embed rings of almost all possible lengths. Besides, there are many situations in which they can embed the most rings of the same length.

The star graph has been recognized as an attractive alternative to the hypercube. Let F/sub e/ and F/sub /spl nu// be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |F/sub e/|/spl les/n-3 (|F/sub /spl nu//|=0), and a ring of length at least n!-4|F/sub /spl nu//| if |F/sub /spl nu//|/spl les/n-3 (|F/sub e/|=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case.

Although many networks have been proposed as the topology of a large-scale parallel and distributed system, most of them are neither expansible nor of equal degree. A network with these two properties will gain the advantages of easy implementation and low cost when it is manufactured. The hypernet, which was proposed by Hwang and Ghosh, represents a family of recursively scalable networks that are both expansible and of equal degree. In addition to the two merits, the hypernet has proven efficient for communication and computation. But, unfortunately, most topological properties and the problem of shortest-path routing for the hypernet are still unsolved. The reason is that the structure of the hypernet is complex and asymmetric, and, especially, no mathematical description was given before. In this paper, considering current hardware restrictions, we concentrate our effort on the hypernet of moderate size. We first give a concise mathematical definition for the hypernet and then solve the following problems for the hypernet of two levels: (1) shortest-path routing, (2) diameter, (3) connectivity, (4) minimum-height spanning trees, and (5) embedding of rings, tori, and hypercubes. © 1998 John Wiley & Sons, Inc. Networks 31:105–118, 1998

Recently, WK-recursive networks have received much attention due to their many favorable properties. However, they suffered from a rigorous restriction on their sizes. Incomplete WK-recursive networks were proposed to relieve this restriction. In this paper, the topological properties of incomplete WK-recursive networks are investigated. It is shown that they contain Hamiltonian cycles if their connectivities are greater than one. A sufficient and necessary condition is also proposed for those with connectivity one to contain a Hamiltonian path. A linear-time algorithm using the prune-and-search technique is presented to compute their diameters. © 1998 John Wiley & Sons, Inc. Networks 32: 23–45, 1998

The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-t=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 proven 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)-1, 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 3/|/spl les/k.

We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance-hereditary graph in O(log/sup 2/ n) time using O(n+m) processors on a CREW PRAM.

Given positive integers κ and l, let R(κ, l) denote the class of interconnection networks so that for any κ + 1 distinct nodes x, y1, y2, …, yκ there exist κ node-disjoint paths (except at x) of length at most l from x to y1, y2, …, yκ, respectively. The Rabin number of a network W with connectivity κ, denoted by rκ(W), is defined as min{l|W ∈ R(κ, l)}. The Rabin number problem is to compute rκ(W) for a given network W. Computing Rabin numbers for nontrivial networks is not easy, in general. Thus far, only the Rabin number of the hypercube has been computed. In this paper, some new results on the Rabin number problem are derived. First, a theorem relating the Rabin number with both wide diameter and fault diameter is obtained. This theorem can help in the derivation of lower bounds for the Rabin numbers of circulant networks, folded hypercubes, hierarchical folded-hypercube networks, generalized hypercubes, and WK-recursive networks. Moreover, upper bounds are also obtained for WK-recursive networks and a special class of generalized hypercubes. The Rabin numbers of a special class of circulant networks and a special class of generalized hypercubes are determined as a consequence of the derived upper and lower bounds. © 1997 John Wiley & Sons, Inc. Networks 30:219–230, 1997

The WK-recursive networks own two structural advantages: expansibility and equal degree. A network is expansible if no changes to node configuration and link connection are necessary when it is expanded, and of equal degree if its nodes have the same degree no matter what the size is. However, the number of nodes contained in a WK-recursive network is restricted to d/sup t/, where d>1 is the size of the basic building block and t/spl ges/1 is the level of expansion. The incomplete WK-recursive networks, which were proposed to relieve this restriction, are allowed to contain an arbitrary number of basic building blocks, while presenting the advantages of the WK-recursive networks. Designing shortest-path routing algorithms for incomplete networks is in general more difficult than for complete networks. The reason is that most incomplete networks lack a unified representation. One of the contributions of this paper is to demonstrate a useful representation, i.e., the multistage graph representation, for the incomplete WK-recursive networks. On the basis of it, a shortest-path routing algorithm is then proposed. With O(d/spl middot/t) time preprocessing, this algorithm takes O(t) time for each intermediate node to determine the next node along the shortest path.

The WK-recursive networks, which were originally proposed by Vecchia and Sanges, have suffered from the rigorous restriction on the number of nodes. Like the other incomplete networks, the incomplete WK-recursive networks have been proposed to relieve this restriction. In this paper, it is first shown that the structures of the incomplete WK-recursive networks are conveniently represented with multistage graphs. This representation can provide a uniform look at the incomplete WK-recursive networks. With its help, a linear-time algorithm using the prune-and-search technique is presented for computing the diameters of the incomplete WK-recursive networks.

We present a parallel recognition algorithm for bipartite-permutation graphs. The algorithm can be executed in O(log n) time on the CRCW PRAM if O(n/sup 3//log n) processors are used, or O(log/sup 2/ n) time on the CREW PRAM if O(n/sup 3//log/sup 2/n) processors are used. Chen and Yesha (1993) have presented another CRCW PRAM algorithm that takes O(log/sup 2/n) time if O(n/sup 3/) processors are used. Compared with Chen and Yesha's algorithm, our algorithm requires either less time and fewer processors on the same machine model, or fewer processors on a weaker machine model. Our algorithm can also be applied to determine if two bipartite-permutation graphs are isomorphic.

In this paper, a new two-level interconnection network, called a hierarchical folded-hypercube network (HFN, for short), is proposed. The HFN takes folded hypercubes as basic modules which are connected in a complete manner. We investigate the topological properties of the HFN, including the diameter, cost, average distance, embedding, connectivity, container, /spl kappa/-wide diameter, and node-fault diameter. We show that the HFN can emulate algorithms which are executable on the ring or the mesh-connected computer with the same time complexities in big-O notation. Moreover, the HFN can embed a folded hypercube having the same number of nodes with constant dilation. We compute the diameter, node connectivity, best container, /spl kappa/-wide diameter, and node-fault diameter of the HFN. We present optimal routing and broadcasting algorithms for the HFN. The semigroup computation and descend/ascend algorithms can be executed as well on the HFN.>

Abstract Recently, with the support of the CAPRI (Concurrent Architecture and PRogramming environment for highly Integrated system) project, Vecchia and Sanges proposed a new general class of recursively scalable networks, termed WK‐recursive networks, and developed routing and broadcasting algorithms on them. They have also implemented the WK‐recursive networks using VLSI technology. This paper studies WK‐recursive networks by first investigating their topological properties such as diameter, connectivity, and Hamiltonicity. We then develop new and more efficient routing and broadcasting algorithms. Our routing algorithm can guarantee the shortest paths. Our broadcasting algorithm is much simpler and requires fewer extra bits to be transmitted. The broadcasting tree of our broadcasting algorithm is of minimal height (equal to the diameter), and each node receives the message exactly once. Moreover, we show the execution of descend/ ascend algorithms on the WK‐recursive networks using the bitonic sort as an illustrative example. © 1994 by John Wiley & Sons, Inc.

Abstract The communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock‐free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.

The algebraic path problem is a general description of a class of problems, including some important graph problems such as transitive closure, all pairs shortest paths, minimum spanning tree, etc. In this work, the algebraic path problem is solved on a processor array with a reconfigurable bus system. The proposed algorithms are based on repeated matrix multiplications. The multiplication of two n*n matrices takes O(log n) time in the worst case, but, for some special cases, O(1) time is possible. It is shown that three instances of the algebraic path problem, transitive closure, all pairs shortest paths, and minimum spanning tree, can be solved in O(log n) time, which is as fast as on the CRCW PRAM.>

Two pumping theorems are derived for a network N of CFSMs (communicating finite state machines). Each pumping theorem describes a set of conditions under which a feasible event sequence of N can be pumped to produce an infinite set of feasible event sequences of N. The authors show that if a feasible event sequence E satisfying the conditions in one pumping theorem does not result in a deadlock or unspecified reception, neither does any event sequence derived by pumping E. Based on these results, they develop a pumping-based approach for detecting deadlocks and unspecified receptions in a network of CFSMs. The experimental results of applying this new approach to validate several communication protocols are shown.>

The problem of finding an optimal assignment of task modules with a precedence relationship in a distributed computing system is considered. The objective of task assignment is to minimize the task turnaround time. The problem is known to be NP-complete for more than three processors. To solve the problem, a well-known state-space reduction technique, branch-and-bound-with-underestimates, is applied, and two underestimate functions are defined. Through experiments, their effectiveness is shown by comparing the proposed algorithm with both Wang and Tsai's (1988) algorithm and the A* algorithm with h(x)=0.>

Semigroup and prefix computations on two-dimensional mesh-connected computers with multiple broadcasting (2-MCCMBs) are studied. Previously, only square 2-MCCMBs with N processing elements were considered for semigroup computations of N data items, and O(N/sup 1/6/) time was required. It is found that square machines are not the best form for semigroup computations, and an O(N/sup 1/8/)-time algorithm is derived on an N/sup 5/8/*N/sup 3/8/ rectangular 2-MCCMB. This time complexity can be further reduced to O(N/sup 1/9/) if fewer processing elements are used. Parallel algorithms for prefix computations with the same time complexities are derived.>

The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O(1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n*n*n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n/sup 2/*n/sup 2/ processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs.>

The authors propose two nonrecursive algorithms for reconstructing the original binary tree from its inorder and preorder traversals. The proposed algorithms proceed in two stages: the first stage establishes the i-p sequence while the second stage reconstructs the binary tree from the i-p sequence. One algorithm, which requires O(N) time, is time-optimal but space-inefficient, while the other requires O(N log N) time and O(N) space. If sorting and binary search are used, then the space required is optimal within a constant factor. If, instead, hashing is used, the computation time required is optimal within a constant factor. Simple modifications of the proposed algorithm can be used to reconstruct the original binary tree from its inorder and postorder traversals.>