Narrow Results

Let $G$ be a simple undirected graph, a set of spanning trees of $G$ are completely independent spanning trees (CISTs for short) if for any two vertices $u,v\in V(G)$, the ($u$, $v$)-paths in these trees have neither vertex nor edge in common, except $u$ and $v$. Hasunuma [1,2] proposed that there are $k$ CISTs in any $2k$-connected graph. However, Péterfalvi [3] disproved this by constructing $k$-connected graphs for $k\ge 2$, which doesn’t have two CISTs. In this paper, we present an algorithm for the construction of three CISTs within the $5$-dimensional folded hypercube ($F{Q}_5$ for short), since $F{Q}_5$ is $6$-connected graph [4]. Moreover, we also provided an approach to construct three CISTs in any $F{Q}_n$ where $n$ is greater than $5$. In particular, for an $F{Q}_{n\ge 6}$ the diameters of the constructed three CISTs are $2n-3$.

The augmented $k$-ary $n$-cube ${AQ}_{n,k}$ is a recently proposed interconnection network that combines the structural characteristics of $k$-ary $n$-cube $Q_n^k$ and augmented cube ${AQ}_n$, with better features. In this paper, we investigate the Hamiltonian properties of augmented $k$-ary $n$-cubes. We prove that the augmented $k$-ary $n$-cube with any $4n-4$ (resp. $4n-5$) faulty edges admits a fault-free Hamilton cycle (resp. Hamilton path).

The exchanged hypercube is regarded as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of the exchanged hypercube $EH(s,t)$$(t\ge s\ge 1)$. We further show the conditional edge fault Hamiltonicity of the exchanged hypercube.

This paper describes a new fault-tolerant routing algorithm for k-ary n-cubes using the concept of "probability vectors". To compute these vectors, a node determines first its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty links. Each node then calculates a probability vector, where the lth element represents the probability that a destination node at distance l cannot be reached through a minimal path due to a faulty node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. An extensive performance analysis conducted in this study reveals that the proposed algorithm exhibits good fault-tolerance properties in terms of the achieved percentage of reachability and routing distances.

This paper proposes a novel routing algorithm, called the direction-first e-cube, for routing on k-ary n-cube interconnection networks. It is an adaptive, partially minimal algorithm based on the wormhole-routing strategy and effectively extends the basic e-cube technique. It has been proved by a set of theorems that the proposed algorithm is deadlock-, livelock- and starvation-free. In the absence of faults, the algorithm is fully minimal. Even in the presence of faults and network congestion, the number of extra hops required to route a message is minimal. The algorithm is also simple to implement, since it utilizes a small header node of 2 log₂ n+n log₂k+1 bits. Simulation results are given to validate the proposed algorithm.

The BGHC is a generalized hypercube that has exactly w nodes along each of the d dimensions for a total of w^d nodes. A BGHC is said to be maximal if the w nodes along each dimension form a complete directed graph. A BGHC is said to be minimal if the w nodes along each dimension form a unidirectional ring. Lower bound complexities are derived for three intensive communication patterns assuming the balanced generalized hypercube (BGHC) topology. A maximal N node BGHC with a node degree equal to αlog₂N, where α≥2, can process certain intensive communication patterns α(α-1) times faster than an N node binary hypercube (which has a node degree equal to log₂N). On the other hand, a minimal N node BGHC with a node degree equal to , where β≥2, is 2^β times slower at processing certain intensive communication patterns than an N node binary hypercube. For certain communication patterns, increasing one unit cost gains a normalized speedup to the binary hypercube by wlog₂w times for the maximal BGHC. For the minimal BGHC, reducing one unit cost gains times speedup normalized to the binary hypercube.

Interconnection networks of various topologies have been widely used in designing multiprocessor architectures. Study of graph theoretical or combinatorial properties of such networks help us better understand them, as well as develop on these architectures more efficient parallel algorithms including fault-tolerant communication/routing algorithms. In this paper, we analyze a broad class of interconnection networks from a new angle by looking into the corresponding graph spectra (i.e., eigenvalues and their multiplicities). Since eigenvalues of the edjacency matrix of a graph can reveal many important properties of the graph that are closely related to its combinatorial invariants, we believe that the study of spectra of interconnection networks can be a more unified approach to studying their topological properties. As a first step) in this direction, here we mainly concentrate on finding out the spectra of some of the most studied interconnection networks. Specifically, after a brief survey of results that relate spectra of graphs to their structural properties, we summarize the existing results for eigenvalues and multiplicities of several popular interconnection networks such as the hypercube and mesh. We also derive some of these results in a more straightforward way. Then we present new results on spectra for some other known networks such as the line graph of the hypercube, followed by experimental results on a few others including the star and pancake networks.

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions.

Dynamically reconfigurable architectures offer extremely fast solutions to various problems. The Circuit Switched Tree (CST) is an important interconnect used to implement such architectures. A CST has a binary tree structure with processing elements (PEs) as leaves and switches as internal nodes. PEs communicate among themselves using the links of the tree. Key components for successful communication are scheduling individual communications and configuring the CST switches. This paper presents a scheduling and configuration algorithm for communications on a CST where conflicts necessitate multiple rounds of routing to perform all communications. The algorithm is distributed and requires only local information, yet it captures the global picture to ensure proper communication. The paper also explains how to apply the algorithm to an important class, "well-nested communications", for which the algorithm is optimal and efficient.

It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit.

The star graph S_n, proposed by [1], has many advantages over the n-cube. It is shown in [2] that when a large number of vertices are deleted from S_n, the resulting graph can have at most two components, one of which is small. In this paper, we show that Cayley graphs generated by transpositions have this property.

In this paper, we propose a solution for the problem of capturing an intruder in two popular interconnection topologies namely, the mesh and the torus. A set of agents collaborate to capture a hostile intruder in the network. While the agents can move in the network one hop at a time, the intruder is assumed to be arbitrarily fast i.e. it can traverse any number of nodes contiguously as far as there are no agents in those nodes. Here we consider a new version of the problem where each agent can replicate new agents when needed, i.e. the algorithm starts with a single agent and new agents are created on demand. We define a new class of algorithms for capturing an intruder. In particular, we propose two different algorithms on mesh and torus networks and we will later discuss about the merits of each algorithm based on some performance criteria.

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions.

A k-container of a graph G is a set of k internally disjoint paths between two distinct vertices. A k-container of G is a k*-container if it contains all vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices, and a bipartite graph G is k*-laceable if there exists a k*-container between any two vertices from different partite sets of G. A k-connected graph (respectively, bipartite graph) G is super spanning connected (respectively, laceable) if G is r*-connected (r*-laceable) for any r with 1 ≤ r ≤ k. This paper shows that the two-dimensional torus Torus(m, n), m, n ≥ 3, is super spanning connected if at least one of m and n is odd and super spanning laceable if both m and n are even. Furthermore, the super spanning connectivity and spanning laceability of tori with faulty elements have been discussed.

The arrangement graph A_n,k is one of the attractive underlying topologies for distributed systems. Let f_m(n, k) be the minimum number of faulty links that make every sub-arrangement graph A_n-m,k-m faulty in A_n,k under link failure model. In this paper, we proved that , , and for 2 ≤ m ≤ k − 2.

The k-isoperimetric edge connectivity is a more refined network reliability index than edge connectivity. The k-isoperimetric edge connectivity of a connected graph G is defined as γ_k(G) = min{|[X, $\overline{X}$]| : X ⊆ V (G), |X| ≥ k, |$\overline{X}$| ≥ k}. Let β_k(G) = min{|[X,$\overline{X}$]| : X ⊆ V (G), |X| = k}. A graph G is called a γ_k-optimal graph if γ_k(G) = β_k(G). An edge cut S = [X,$\overline{X}$] is called a γ_k-cut if |S| = γ_k(G), X ⊆ V (G), |X| ≥ k and |$\overline{X}$| ≥ k. Moreover, G is called a super-γ_k graph if every γ_k-cut [X,$\overline{X}$] of G has the property that either |X| = k or |$\overline{X}$| = k. Let G be a graph of order at least 2k with k ≥ 2. In this paper, we prove that for any pair u, υ of nonadjacent vertices in G, if |N(u)∩N(υ)| ≥ k+1 when neither u nor υ lies on a triangle, or |N(u)∩N(υ)| ≥ 2k -1 when u or υ lies on a triangle, then G is γ_k-optimal. Moreover, if G is a triangle-free graph, and |N(u)∩υ(υ)| ≥ k +1 for all pairs u, υ of nonadjacent vertices in G, then G is either super-γ_k or isomorphic to K_k+1,k+1.

The (s+t+1)-dimensional exchanged crossed cube, denoted by ECQ(s, t), proposed by Li et al., combines the advantages of the hypercube and the crossed cube. It has been proven that ECQ(s, t) has better properties than the fundamental hypercube in the aspects of the fewer edges, lower cost factor and smaller diameter. This paper studies the embedding of cycles in ECQ(s, t). It is proved that ECQ(s, t) contains an l-cycle of every length l from 4 to 2^s+t+1 except that ECQ(2, 3) and ECQ(3, 3) do not contain a cycle of length 9 where $s\ge 2$ and $t\ge 3$. This result reveals the fact that ECQ(s, t) nearly remains the cycle embedding capability, while it only has about half edges of crossed cube.

The generalized hypercube is a highly-connective network proposed by Bhuyan and Agrawal. In this paper, we study the restricted connectivity and fault-free unicast algorithm in the generalized hypercube. Firstly, we prove that the restricted connectivity of a $r$-dimensional generalized hypercube $G(m_r,m_{r-1},\dots ,m_1)$ is $2\kappa (G)-n$, where $\kappa (G)$ denotes the connectivity of $G(m_r,m_{r-1},\dots ,m_1)$ and $n=$ max $\{m_1,m_2,\dots ,m_r\}$, under the condition that each vertex has at least one fault-free neighbor. It is almost twice the traditional connectivity of $G(m_r,m_{r-1},\dots ,m_1)$. Furthermore, we present an $O(\kappa {(G)}^3)$ fault-free unicast algorithm in the generalized hypercube.

For an integer $\ell \ge 2$, the $\ell$-component connectivity of a graph $G$, denoted by ${\kappa }_{\ell }(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $\ell$ components or a graph with fewer than $\ell$ vertices. This naturally generalizes the classical connectivity of graphs defined in term of the minimum vertex-cut. This kind of connectivity can help us to measure the robustness of the graph corresponding to a network. The hierarchical star networks $H{S}_n$, proposed by Shi and Srimani, is a new level interconnection network topology, and uses the star graphs as building blocks. In this paper, by exploring the combinatorial properties and fault-tolerance of $H{S}_n$, we study the $\ell$-component connectivity of hierarchical star networks $H{S}_n$. We obtain the results: ${\kappa }_3(H{S}_n)=2n-2$, ${\kappa }_4(H{S}_n)=3n-3$ and ${\kappa }_5(H{S}_n)=4n-5$ for $n\ge 5$.

The $k$-ary $n$-cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. A many-to-many $m$-disjoint path cover ($m$-DPC for short) of a graph is a set of $m$ vertex-disjoint paths joining two disjoint vertex sets $S$ and $T$ of equal size $m$ that altogether cover every vertex of the graph. The many-to-many $m$-DPC is classified as paired if each source in $S$ is further required to be paired with a specific sink in $T$, or unpaired otherwise. In this paper, we consider the unpaired many-to-many $m$-DPC problem of faulty bipartite $k$-ary $n$-cube networks $Q_n^k$, where the sets $S$ and $T$ are chosen in different parts of the bipartition. We show that, every bipartite $Q_n^k$, under the condition that $f$ or less faulty edges are removed, has an unpaired many-to-many $m$-DPC for any $f$ and $m\ge 1$ subject to $f+m\le 2n-1$. The bound $2n-1$ is tight here.