The process of merging two arbitrary partitions of a given finite set 𝒰 of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions 𝒳, 𝒴 of the set 𝒰 such that 𝒳 = {𝒳 1 , 𝒳 2 , ..., 𝒳 x } and 𝒴 = {𝒴 1 , 𝒴 2 , ..., 𝒴 y }, and determine a new partition 𝒵 = {𝒵 1 , 𝒵 2 , ..., 𝒵 z } such that each is a common non-empty subset of some 𝒳 a ∈ 𝒳 and some 𝒴 b ∈ 𝒴 and |𝒵| is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O( t( n) + log n) parallel time using max { n log n , p ( n ) } processors, where t( n) denotes the running time of a parallel stable sorting algorithm that uses p( n) processors on an EREW PRAM. This result depends on t( n) and p( n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O ( log n log ( n log n ) ) parallel time using n log n processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm.

Abstract Wireless communication has become omnipresent in the world and enables users to have an unprecedented ability to communicate any time and any place. In this article, we propose a mobility model for studying wireless communication. The model incorporates elements such as users, access points, and obstacles so that it faithfully mimics the real environment. Interesting problems that have practical applications are posed and solved. More specifically, we study the complexity of three problems in a grid. The source reachability problem (SRP) models a situation in which we want to determine whether two access points can communicate at a certain time in a mobile environment. When users are involved in this situation, we call this problem the user communication problem (UCP). We show that SRP can be solved in O(max{d,t}m2) time, where d is the number of obstacles, t is the time bound in the statement of the problem, and m is the number of access points; we show that UCP can be solved in O(max{d,t}m4) time. The third problem called the user communication, limited source access problem (UCLSAP) studies a situation where we want to determine whether two users can communicate uninterruptedly during the duration of the model while considering battery‐time limits of the access points. In contrast to the first two problems, we demonstrate that UCLSAP is intractable, unless P = NP. In conclusion, we briefly discuss the extension of our model to three dimensions and provide a list of open problems. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012