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.

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.

The growth in the amount of information available on the Internet and thousands of user queries per second brings huge challenges to the index update and query processing of search engines. Index compression is partially responsible for the current performance achievements of existing search engines. The selection of the index compression algorithms must weigh three factors, i.e., compression ratio, compression speed and decompression speed. In this paper, we study the well-known Simple-9 compression, in which exist many branch operations, table lookup and data transfer operations when processing each 32-bit machine word. To enhance the compression and decompression performance of Simple-9 algorithm, we propose a successive storage structure and processing metric to compress two successive Simple-9 encoded sequence of integers in a single data processing procedure, thus the name Successive Simple-9 (SSimple-9). In essence, the algorithm shortens the process of branch operations, table lookup and data transfer operations when compressing the integer sequence. More precisely, we initially present the data storage format and mask table of SSimple-9 algorithm. Then, for each mode in the mask table, we design and hard-code the main steps of the compression and decompression processes. Finally, analysis and comparison on the experimental results of the simulation and TREC datasets show the compression and decompression efficiency speedup of the proposed SSimple-9 algorithm.

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.