Search

The hypercube is one of the most popular interconnection networks. Its network cost is O (n 2) . In this paper, we propose a new hypercube variant, the divide-and-swap cube DSC (n) (n = 2 d , d ≥ 1) , which reduces the network cost to O (n log n) while maintaining the same number of nodes and the same asymptotic performances for fundamental algorithms such as the broadcasting. The new network has nice hierarchical properties. We first show that the diameter of DSC (n) is lower than or equal to 5 n 4 - 1 . However, unlike the hypercube of dimension n whose degree is n, the node degree of the network is log n + 1 , resulting in a network cost of O (n log n) . We then examine the one-to-all and all-to-all broadcasting times of DSC (n) , based on the single-link-available and multiple-link-available models. We also present an upper bound on the bisection width of the DSC (n) and show that DSC (n) is Hamiltonian. Finally, we introduce the folded divide-and-swap cube, FDSC (n) , a variant of the DSC (n) and study its many properties including its hierarchical structure, routing algorithm, broadcasting algorithms, bisection width, and its Hamiltonicity. All the broadcasting algorithms presented in this paper are asymptotically optimal. [ABSTRACT FROM AUTHOR]

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has 10n nodes and 2.5×10n edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are 3log10N-1 and 15log10N-1, respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FPk with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require O(N) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and O(log10N) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm for sorting n pancakes. The previous studies were focused on finding upper bound or lower bound regarding a limited n-pancake. This study, however, suggests the algorithms for n-pancake with $$n\ge 5$$ . The only constraint is that $$n\ge 5$$ , which eliminates the very strong constraints [ $$n\equiv 0$$ (mod 16), $$n\equiv 0$$ (mod 14), $$n\equiv 3$$ (mod 4), etc.] that were used in previous studies. In addition, the sorting cost of the proposed algorithm is almost a half, from other existing studies, despite the fact that it reduces the degree from $$n-1$$ to $$\frac{n}{2}+1$$ . We define the term 'restricted reversal', and based on that terminology, we also propose simple sorting and improved sorting algorithms for the pancake sorting. Further, we examine the worst case time complexity and average time to complete a sort using the suggested algorithms. We also propose sorting costs for the evaluation of similar sorting algorithms such as pancake, burnt pancake, and signed permutation algorithms, and compare the sorting costs and constraints that were found in existing studies. In addition, we propose a burnt pancake sorting algorithm that employs the proposed restricted reversals. [ABSTRACT FROM AUTHOR]

Routing and broadcasting are major parameters determining the performance of interconnection networks. In this paper, we propose a new Petersen-torus network $$\mathrm{NPT}(m, n)$$ by modifying the external edge definitions of the Petersen-torus network to improve its diameter and broadcasting times. We also show one-to-all broadcasting algorithms in $$\mathrm{NPT}(m, n)$$ using the single-link available and multiple-link available models. [ABSTRACT FROM AUTHOR]

The hyper-torus network based on a three-dimensional hypercube was introduced recently. The hyper-torus $$QT(m,n)$$ performs better than mesh type networks with a similar number of nodes in terms of the network cost. In this paper, we prove that if $$n$$ is even, the bisection width of $$QT(m,n)$$ is $$6n$$ , whereas it is $$6n+2$$ if it is odd. Second, we show that $$QT(m,n)$$ contains a Hamiltonian cycle. In addition, its one-to-all and all-to-all broadcasting algorithms are introduced. All of these broadcasting algorithms are asymptotically optimal. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. The designs of multiple ISTs on several classes of networks have been widely investigated. In this paper we show a construction algorithm of ISTs on odd graphs, and we analyze that all the lengths of the paths in the ISTs are less than or equal to the length of the shortest path+4, which is optimal. We also prove that the heights of the ISTs we constructed are d+1, which again is optimal, since the fault diameter of an odd graph is d+1. [ABSTRACT FROM AUTHOR]