The complete multipartite graph and the complete multi-layered graph are both generalizations of the complete bipartite graph. These two kinds of graphs have recursive structure and offer a very flexible choice of network size with respect to a fixed network order. This paper addresses the genus of the complete multipartite graph and the complete multi-layered graph which measures how efficiently we can set up a computer network using these graph layouts.

Both the pancake graph and star graph are Cayley graphs and are especially attractive for parallel processing. They both have sublogarithmic diameter, and are fairly sparse compared to hypercubes. In this paper, we focus on another important property, namely the genus. The genus of a graph is the minimum number of handles needed for drawing the graph on the plane without edges crossing. We will investigate the upper bound and lower bound for the genus of pancake graph and compare these values with the genus of the star graph as well as that of the hypercube.

Recently, many flooding techniques for Mobile Ad Hoc Networks (MANETs) have been proposed. However, most of these techniques assume that every node in the network has the same transmission range. Therefore, these techniques have poor performance when the nodes in the network have different transmission ranges. In this paper, we propose a new flooding technique to support nodes with different transmission ranges in MANETs. In our technique, when a node receives a packet it avoids an unnecessary retransmission by both checking if all its 1-hop neighboring nodes have received the same packet or if all its transmission area has been covered by the packet sender. In addition, a node avoids unnecessary delay by transmitting immediately if it has the greatest additional coverage area among all the nodes in the 1-hop neighborhood. We compared our technique with similar ones and simulation results using ns-2 show that our technique, using the features mentioned above, substantially reduces the number of unnecessary retransmissions and the delivery latency while maintaining high network coverage.

Group multicast is becoming a prevalent issue in network applications such as teleconferencing, pay-per-view, and information services. In order to secure group communications by providing confidentiality and trustworthiness of messages, various methods were proposed in the literature. In this paper, we compare some of these methods. In particular, we consider the exclusive basis systems, and the batch re-keying methods. We also simulate the process of subgroup eviction for exclusion basis system (EBS) and we compare the work that needs to be done in a group-join and a group-eviction both in EBS and in batch re-keying process. The comparisons of EBS with algorithms for batch re-keying process show that for group eviction batch process is more efficient while EBS is for group join

In this paper, we present an efficient algorithm to solve the orientation optimization problem for a layered wheel floorplan. The strategy used is to generate all the nonredundant implementations for the floorplan. The computational complexities of the algorithm depend on the actual dimensions of the cells in the floorplan. In the best case, it takes O(n2) time and O(n) space, where n is the number of layers in the floorplan. In the worst case, it takes O(2n) time and O(2n) space. Furthermore, we prove that the time and space complexities for the worst case are optimal. A set of conditions is obtained to check whether the floorplan belongs to the worst case. Using these conditions, we show that even though the worst case is theoretically unavoidable it is not encountered in practical situations where the cell dimensions are bounded. © 1999 John Wiley & Sons, Inc. Networks 34: 67–72, 1999

The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n).

The recently introduced interconnection network, crossed cube, has attracted much attention in the parallel processing area due to its many attractive features. Like the ordinary hypercube, the n-dimensional crossed cube is a regular graph with 2/sup n/ vertices and n2/sup n-1/ edges. The diameter of the crossed cube is approximately half that of the ordinary hypercube. These advantages of the crossed cube motivated the study of how well it can simulate other networks such as the complete binary tree. We show that the (2/sup n/-1) node complete binary tree can be embedded into the n-dimensional crossed cube with dilation 1.>

The star graph has recently been suggested as an alternative to the hypercube. The star graph has a rich structure and symmetry properties as well as desirable fault-tolerant characteristics. The star graph's maximum vertex degree and diameter, viewed as functions of network size, grow less rapidly than the corresponding measures in a hypercube. We investigate the genus of the star graph and compare it with the genus of the hypercube.>