We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to v securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, when a certificate graph and a set of communication requests are given, we consider the problem to disperse the certificates among the nodes in the network, such that the communication requests are satisfied and the total number of certificates stored in the nodes is minimized. We formulate this problem as MINIMUM CERTIFICATE DISPERSAL (MCD for short). We show that MCD is NP-Complete, even if its input graph is restricted to a strongly connected graph. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs, when the communication requests satisfy some restrictions. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, and some Cartesian products of graphs.

We consider an initialization problem in single-hop radio networks. The initialization is the task of assigning distinct ID numbers to nodes in a network. We have greatly improved the previous results [10] for the initialization in an n-node network. We propose randomized initialization algorithms in two cases. The first case is that n is known to all the nodes and the second case is that n is unknown to all the nodes. The algorithm for the first case completes in en+ln n+O (1) expected time slots, and the algorithm for the second case completes in en+O() expected slots. The main idea of the algorithm for the case that n is unknown is presumption of the number of nodes. In the algorithm, each node presumes the number of nodes efficiently and is assigned ID by using the algorithm for the case that n is known with the presumption value.

This paper considers a neighborhood broadcasting protocol in undirected de Bruijn and Kautz networks. The neighborhood broadcasting problem(NBP) is the problem of disseminating a message from an originator vertex to only its neighbors. Our protocol works under the single-port and half-duplex model and solves NBP in 5log2(n+1) + O(1) time units on the undirected de Bruijn graph UB(n,d) with nd vertices and the undirected Kautz graph UK(n,d) with nd + nd-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k nε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k nε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O((n α(n) log3 n)/p) time using p processors, where 1 p n1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ε-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+42)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.

A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.

In this paper, we focus on the problem that in an ad hoc network, how to send a message securely between two users using the certificate dispersal system. In this system, special data called certificate is issued between two users and these issued certificates are stored among the network. Our final purpose on this certificate dispersal problem is to construct certificate graphs with lower dispersability cost which indicates the average number of certificates stored in each node in an ad hoc network. As our first step, when a certificate graph is given, we construct two efficient certificate dispersal algorithms for strongly connected graphs and directed graphs in this paper. We can show that for a strongly connected graph G =(V, E) and a directed graph H =(V ′, E ′), new upper bounds on dispersability cost on the average number of certificates stored in one node are O(DG +|E|/|V|) and O(pG dmax +|E ′|/|V ′|) respectively, where DG is the diameter of G, dmax is the maximum diameter of strongly connected components of H and pG is the number of strongly connected components of H. Furthermore, we give some new lower bounds for the problem and we also show that our algorithms are optimal for several graph classes.

Multi-level divide-and-conquer (MDC) is a generalized divide-and-conquer technique, which consists of more than one division step organized hierarchically. In this paper, we investigate the paradigm of the MDC and show that it is an efficient technique for designing parallel algorithms. The following parallel algorithms are used for studying the MDC: finding the convex hull of discs, finding the upper envelope of line segments, finding the farthest neighbors of a convex polygon and finding all the row maxima of a totally monotone matrix. The third and the fourth algorithms are newly presented. Our discussion is based on the EREW PRAM, but the methods discussed here can be applied to any parallel computation models.