Search

Let = { T 1 , T 2 , ... , T k } be a set of k ≥ 2 spanning trees in a graph G. The k spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, is called a dual-CIST provided k = 2. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. This paper investigates the problem of constructing a dual-CIST in the n -dimensional hierarchical folded cubic network H F Q n . The network is a two-level network using folded hypercube F Q n as clusters to reduce the diameter, hardware overhead and improve the fault tolerance ability. We propose a recursive algorithm to construct a dual-CIST of H F Q n in (2 2 n) time for n ≥ 2 , where the time required is the same scale as the number of vertices of H F Q n . Also, the diameter of each constructed CIST is 4 n + 1. [ABSTRACT FROM AUTHOR]

In IP networks, packet forwarding is destination-based and hop-by-hop, and routes are built as needed. Kwong et al. introduced a protection routing in which packet delivery to the destination node can proceed uninterrupted in the event of any single node or link failure. He then showed that "whether there is a protection routing to the destination" is NP-complete. Tapolcai found that two completely independent spanning trees, abbreviated as CISTs, can be used to configure the protection routing. In this paper, we proposed dual protection routing trees, denoted as dual-PRTs to replace CISTs, which are less restrictive than CISTs. Next, we proposed a transformation algorithm that uses dual-PRTs to configure the protection routing. Taking complete graphs Kn, complete bipartite graphs Km,n, hypercubes Qn, and locally twisted cubes LTQn as examples, we provided a recursive method to construct dual-PRTs on them. This article showed that there are no two CISTs on K3,3, Q3, and LTQ3, but there exist dual-PRTs that can be used to configure the protection routing. As shown in the performance evaluation of simulation results, for both Qn and LTQn, we get the average path length of protection routing configured by dual-PRTs is shorter than that by two CISTs. [ABSTRACT FROM AUTHOR]

The protection routing uses the multi-paths technique for integrating route discovery and route maintenance mechanisms in a network, and thus it can tolerate the failure of one component (including a node or a link). Tapolcai (2013) proposed a method showing that a network possessing two completely independent spanning trees (CISTs for short) suffices to configure a protection routing. However, it is well-known that the problem of determining whether there exist two CISTs in a graph (or network) is NP-complete. In this paper, we extend Tapolcai's method such that the protection routing is configured by a combination of multiple CISTs. The first application of such an extension is that it can be used to deal with the problem of security in transmission, which we call the secure-protection routing scheme (SPR-scheme for short). Thus, a network transmission using the SPR-scheme ensures that no node other than the destination can receive the complete message. Moreover, we show that if a message M is transmitted in a network G using the SPR-scheme configured by a combination of n CISTs, then each intermediate node of G can receive a maximum of 2 ∕ n ratio of M. From a similar idea of the extension, another application is the so-called multiple-protection routing scheme (MPR-scheme for short) which can be used to increase the capability of fault-tolerance. For assessing the performance of routing using MPR-scheme, we first propose a construction of three CISTs in the two types of Möbius cubes, which are hypercube-variant networks and are superior to hypercubes due to having a smaller diameter. For the n -dimensional Möbius cube, the diameters of CISTs we constructed are at most 14 when n = 6 and at most 2 n + 1 when n ⩾ 7. So, we configure the desired protection routing in the Möbius cubes via the three CISTs. Then, we provide simulation results to experimentally evaluate the performance of the newly proposed MPR-scheme in the n -dimensional Möbius cubes for 6 ⩽ n ⩽ 10. As an important point, our results show that the adoption of routing using MPR-scheme will result in a significant slowdown in the transmission failure rate. • We propose a construction of three CISTs in a Möbius cube M Q n . • For n ⩾ 7 , the diameters of three CISTs of M Q n we constructed are at most 2n+1. • Protection routing employing MPR-scheme can increase the capability of fault-tolerance. • Protection routing using SPR-scheme ensures that no node other than the destination can receive the complete message. [ABSTRACT FROM AUTHOR]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

A set of $k~(\geqslant 2)$ spanning trees in the underlying graph of a network topology is called completely independent spanning trees, (CISTs for short), if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if $k=2$ , the two CISTs are called a dual-CIST. However, it has been proved that determining if there exists a dual-CIST in a graph is an NP-hard problem. Kwong et al. [IEEE/ACM Transactions Networking 19(5) 1543–1556, 2011] defined that a routing is protected, if there is an alternate with loop-free forwarding, when a single link or node failure occurs. Shortly afterward, Tapolcai [Optim. Lett. 7(4) 723–730, 2013] showed that a network possessing a dual-CIST suffices to establish a protection routing. It is well-known that Cayley graphs have a large number of desirable properties of interconnection networks. Although many results of constructing dual-CISTs on interconnection networks have been proposed in the literature, so far, the work has not been dealt with on Cayley graphs due to that their expansions are in exponential scalability. In this paper, we try to make a breakthrough of this work on some famous subclasses of Cayley graphs, including alternating group networks, bubble-sort network, and star networks. We first propose tree searching algorithms for helping the construction of dual-CISTs on low-dimensional networks. Then, by inductive construction, we show that dual-CISTs on high-dimensional networks can also be constructed agreeably. As a result, we can configure protection routings by using the constructed dual-CISTs. In addition, we complement some analysis with a simulation study of the proposed construction to evaluate the corresponding performance. [ABSTRACT FROM AUTHOR]

Given a graph G , a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any two vertices x , y ∈ V ( G ) , the paths joining x and y on these trees have neither vertex nor edge in common, except x and y . Hasunuma [9,10] first introduced the concept of CISTs and conjectured that there are k CISTs in any 2 k -connected graph. Unfortunately, Péterfalvi [16] disproved this conjecture by constructing a k -connected graph, for each k ⩾ 2 , which does not have two CISTs. In this paper, we provide a unified approach for constructing two CISTs in several hypercube-variant networks, including hypercubes, locally twisted cubes, crossed cubes, parity cubes, and Möbius cubes. In particular, for an n -dimensional hypercube-variant network, the diameters of the constructed CISTs are 2 n − 1 . [ABSTRACT FROM AUTHOR]

• We investigate the problem of constructing a dual-CIST on bicubes B Q n. • A newly generic adjustment scheme can reduce the diameter of dual-CIST. • The diameter of the constructed dual-CIST of B Q n is 2 n − 2 for n ⩾ 5 odd. • The diameter of the constructed dual-CIST of B Q n is 2 n − 3 for n ⩾ 6 even. • As a by-product, a folded hypercube F Q n admits a dual-CIST with diameter 2 n − 2. Recently, an innovative hypercube-variant network called bicube, denoted as B Q n , has been proposed to possess both short diameter and symmetry advantages. Unlike other existing hypercube-variant networks, they lose their symmetry in pursuit of short diameters. For solving the problems of fault-tolerant transmission and secure message distribution in a reliable network, one solution suggested a dual-CIST (two completely independent spanning trees) to design a multi-path routing (e.g., a recently proposed secure-protection routing). We can make the construction using the standard arrangement guideline (SAG) like the hypercubes to obtain a dual-CIST with a diameter of 2 n − 1 on B Q n. This paper proposes a newly generic adjustment scheme (GAS) for reducing the diameter of the dual-CIST under this construction. As a result, the diameter of T i for i = 1 , 2 we constructed for B Q n are as follows: diam (T i) = { 7 if n = 4 ; 2 n − 2 if n ⩾ 5 and n is odd ; 2 n − 3 if n ⩾ 6 and n is even. [ABSTRACT FROM AUTHOR]

Spanning trees T 1 , T 2 , ... , T k (k ≥ 2) in a graph G are called completely independent spanning trees (CISTs for short) if for any two vertices x , y of G , the paths joining x and y in these k trees are pairwise openly disjoint. Hong and Zhang (2018) recently showed that a sufficient condition for Hamiltonian graphs still suffices for the existence of two CISTs. That is, if G is a graph with n vertices and | N (x) ∪ N (y) | ≥ n 2 , | N (x) ∩ N (y) | ≥ 3 for every two nonadjacent vertices x , y of G and n ≥ 5 , then G admits two CISTs. In this note, we first attend that the restriction on the number of vertices in the statement should be revised. Moreover, we point out that there is a flaw in their proof. Accordingly, we give an amendment to correct the proof. [ABSTRACT FROM AUTHOR]