Journal of Interconnection Networks

Tori are important fundamental interconnection networks for multiprocessor systems. Hamiltonian paths are important in information communication of multiprocessor systems, and Hamiltonian path embedding capability is an important aspect to determine if a network topology is suitable for a real application. In real systems, some links may have better performance. Therefore, when embedding Hamiltonian path into interconnection networks, it is desirable that these Hamiltonian paths would pass through the links with better performance. Given a two two-dimensional torus T (m, n) with m, n ≥ 5 odd, let L be a linear forest with at most two edges in T (m, n) and let u and v be two distinct vertices in T (m, n) such that none of the paths in L has u or v as internal node or both of them as end nodes. In this paper, we construct a hamiltonian path of T (m, n) between u and v passing through L.

This study presents a new method based on the imperialist competitive algorithm (ICA-based) to solve the k-coverage and m-connected problem in wireless sensor networks (WSNs) through the least sensor node count, where the candidate positions for placing nodes are pre-specified. This dual featured problem in WSNs is a nondeterministic polynomial (NP)-hard problem therefore, ICA the social-inspired evolutionary algorithm is assessed and ICA-based scheme is designed to solve the problem. This newly proposed ICA-based scheme provides an efficient algorithm for representing the imperialistic competition among some of the best solutions to the problem in order to decrease the network cost. The mathematical formulation is presented for the node placement problem. The main issue of concern here is the deployed sensor node count. The simulation results confirm that ICA-based method can reduce the required sensor node count unlike other genetic-based and biogeography-based evolutionary algorithms. The experimental results are presented for WSN_Random and WSN_Grid scenarios.

The g-extra connectivity of a multiprocessor system modeled by a graph G, denoted by ${\kappa }_o^{(g)}$ (G), is the minimum number of removed vertices such that the network is disconnected and each residual component has no less than g + 1 vertices. The t/k-diagnosis strategy can detect up to t faulty processors which might include at most k misdiagnosed processors. These two parameters are important to measure the fault tolerant ability of a multiprocessor system. The extra connectivity and t/k-diagnosability of many well-known networks have been investigated extensively and independently. However, the general relationship between the extra connectivity and the t/k-diagnosability of general regular networks has not been established. In this paper, we explore the relationship between the k-extra connectivity and t/k-diagnosability for regular networks under the classic PMC diagnostic model. More specifically, we derive the relationship between 1-extra connectivity and pessimistic diagnosability for regular networks. Furthermore, the t/k-diagnosability and pessimistic diagnosability of some networks, including star network, BC networks, Cayley graphs generated by transposition trees etc., are determined.

The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adjacent vertices is minimized. The minimum value of this optimization problem gives rise to a graph invariant σ(G), called the tree-stretch of G. The problem has been proved NP-hard. In this paper we present a general approach to determine the exact values σ(G) for a series of typical graphs arising from communication networks, such as Hamming graphs and higher-dimensional grids (including hypercubes).