Summary We present a simple recurrence for the surface area of the ‐star graph, , that is, the number of nodes at a certain distance from the identity node in the graph, an important parameter for interconnection networks in parallel computing. The family of the ‐star graphs includes several popular interconnection networks such as the star graph and the alternating group network. Previously, a surface area recurrence has been obtained for a special case, for example, when , in the family of ‐star. Our recurrence gives one single recurrence for all graphs in the family, thus completely solving the surface area of ‐star for all . Compared to explicit surface area formulas previously obtained through complicated and involved combinatorial analysis and generating function approach, our derivation is more elementary and our recurrence gives a way to compute the surface area of the ‐star efficiently.

An important invariant of an interconnection network is its surface area, the number of vertices at distance i from a node. Although much work has been done to obtain formulas for the surface areas for many interconnection networks, most of the formulas are not in the so-called closed form except for a very few trivial graphs. It is known that for an interconnection network, if its surface area satisfies the so-called forward difference property, then for any specific distance i, its surface area of radius i in closed form (a polynomial of degree i) can be obtained, provided that we have i + 1 initial values of the surface area of radius i. This property is known to hold for the hypercube and the star graph. We show in this paper that the property also holds for the (n, k)-star graph, 1 ≤ k ≤ n − 1, a family of interconnection networks that also include the star graph when k = n − 1. We then show that the technique we use for the result is general that can also be used to prove the property for some other networks.

Summary We investigate fault‐tolerant shortest path problem in the hypercube between two nodes where some nodes are faulty (or blocked) and thus cannot be used in routing. Previously, several similar problems were studied where proposed algorithms are distributed and local‐information‐based, that is, each node in the network knows only its neighbor's status (faulty or not) and they also look for optimal or near‐optimal paths. There have been studies that established some sufficient conditions for these paths to exist. Since these conditions are only sufficient, there could be shortest paths that will be missed by these conditions. We study the problem under the assumption that for two given nodes, a source node s, a target node t, only s requires to have a global information of the network in order to find a shortest path to t, should it exist. A shortest path is defined as the Hamming distance between s and t. This problem can be solved by trivial algorithms. The first is to try all possible paths. In an n‐dimensional hypercube with 2n vertices, this method would cost at least n! time. Another method is to perform a standard shortest path finding algorithm, which would require at least 2n time. A routing algorithm has been previously developed which is efficient in certain situations. However, in the worst case, its running time could be exponential in the hypercube dimension. We propose an efficient algorithm with running time of O(n3m2), polynomial in n, the hypercube dimension, and m, number of blocking nodes. We gain our efficiency by reducing the routing problem to a permutation problem which can be solved using inclusion‐exclusion principle. We finally use dynamic programming technique to optimally count the terms. With the proposed algorithm, not only can we find a shortest path, if such a path does exist, but we can also count all possible shortest paths.

Summary Hyper‐star graph HS(2n,n) was introduced to be a competitive model to both hypercubes and star graphs. In this paper, we study its properties by (1) giving a closed form solution to the surface area of HS(2n,n), (2) discussing its Hamiltonicity by establishing an isomorphism between the graph and the well‐known middle levels problem, and (3) showing that full binary trees can be embedded into HS(2n,n) with dilation 1. We also develop a single‐port optimal neighbourhood broadcasting algorithm for HS(2n,n). Copyright © 2015 John Wiley & Sons, Ltd.

An important and interesting parameter of an interconnection network is the number of vertices of a specific distance from a specific vertex. This is known as the surface area or the Whitney number of the second kind. It turns out that, in some applications, the number of vertices of a specific distance from a subgraph H is also important. A fundamental starting point is to consider the number of vertices of a specific distance from an edge, which is called the edge surface area. In this paper, we give an explicit formula for the edge surface area of arrangement graphs via the generating function technique. As a direct consequence, it will also provide such explicit formulas for star graphs, alternating group graphs and split stars.

The arrangement graph is a generalization of the well known star graph and the alternating group graph. We first resent a constant time routing algorithm that allows two groups of sub-arrangement graphs to exchange their data in a one-to-one fashion. We then use this routing algorithm to develop an optimal broadcasting algorithm, an optimal algorithm for computing the general prefix sums as well as an efficient sorting algorithm on the arrangement graph. Consequently, all of our algorithms are applicable to the star and the alternating group graphs.

We present a routing algorithm that finds n disjoint shortest paths from the source node to n target nodes in the n-dimensional hypercube in O(n3log n)=O(log3NloglogN) time, where N=2n, provided that such disjoint shortest paths exist which can be checked in O(n5/2) time, improving the previous O(n4) routing algorithm.

Abstract The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.