Constructing independent spanning trees for locally twisted cubes

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ_n. The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ_n. However, we find out that LTQ_n is not vertex-transitive when n≥4; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for LTQ_n. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ_n; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ_n.     

Regular connected bipancyclic spanning subgraphs of hypercubes

An n-dimensional hypercube Q_n is a Hamiltonian graph; in other words Q_n (n≥2) contains a spanning subgraph which is 2-regular and 2-connected. In this paper, we explore yet another strong property of hypercubes. We prove that for any integer k with 3≤k≤n, Q_n (n≥3) contains a spanning subgraph which is k-regular, k-connected and bipancyclic. We also obtain the result that every mesh P_m×P_n (m,n≥2) is bipancyclic, which is used to prove the property above.     

Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. Hsieh and Tu [S.-Y. Hsieh, C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. In this paper, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.     

On embedding subclasses of height-balanced trees in hypercubes

A height-balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Q_h+1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not.     

Reducing the Height of Independent Spanning Trees in Chordal Rings

This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex v neq r, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. [CHECK END OF SENTENCE] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided.     

Cover1

This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex vner, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. (1999) proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

Constructing edge-disjoint spanning trees in twisted cubes

The use of edge-disjoint spanning trees or independent spanning trees in a network for data broadcasting has the benefits of increased of bandwidth and fault-tolerance. In this paper, we propose an algorithm which constructs n edge-disjoint spanning trees in the n-dimensional twisted cube, denoted by TQ_n. Because the n-dimensional twisted cube is n-regular, the result is optimal with respect to the number of edge-disjoint spanning trees constructed. Furthermore, we also show that of the n edge-disjoint spanning trees constructed are independent spanning trees. This algorithm runs in time O(N log N) and can be parallelized to run in time O(log N) where N is the number of nodes in TQ_n.     

Linear array and ring embeddings in conditional faulty hypercubes

The n-dimensional hypercube Q_n is a graph having 2ⁿ vertices labeled from 0 to 2ⁿ−1. Two vertices are connected by an edge if their binary labels differ in exactly one bit position. In this paper, we consider the faulty hypercube Q_n with n⩾3 that each vertex of Q_n is incident to at least two nonfaulty edges. Based on this requirement, we prove that Q_n contains a hamiltonian path joining any two different colored vertices even if it has up to 2n−5 edge faults. Moreover, we show that there exists a path of length 2ⁿ−2 between any two the same colored vertices in this faulty Q_n. Furthermore, we also prove that the faulty Q_n still contains a cycle of every even length from 4 to 2ⁿ inclusive.     

Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover, the proof of its correctness is simpler than that of Yang et al.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. 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 u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

Algorithms for updating minimal spanning trees

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n²) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing4 (1975), 375–380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n²) steps. If all the vertices are considered, O(n³) steps may be used. The algorithm which we present here takes only O(n²) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge.     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

On the diameter of geometric path graphs of points in convex position

For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,Q∈P(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. [S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.     

How to Use Spanning Trees to Navigate in Graphs

In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N _G [v] in G (or, k-neighborhood D _k (v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.     

Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes

Independent spanning trees (ISTs) on networks have applications to increase fault-tolerance, bandwidth, and security. Möbius cubes are a class of the important variants of hypercubes. A recursive algorithm to construct n ISTs on n-dimensional Möbius cube M _n was proposed in the literature. However, there exists dependency relationship during the construction of ISTs and the time complexity of the algorithm is as high as O(NlogN), where N=2 ⁿ is the number of vertices in M _n and n≥2. In this paper, we study the parallel construction and a diagnostic application of ISTs on Möbius cubes. First, based on a circular permutation n?1,n?2,…,0 and the definitions of dimension-backbone walk and dimension-backbone tree, we propose an O(N) parallel algorithm, called PMCIST, to construct n ISTs rooted at an arbitrary vertex on M _n . Based on algorithm PMCIST, we further present an O(n) parallel algorithm. Then we provide a parallel diagnostic algorithm with high efficiency to diagnose all the vertices in M _n by at most n+1 steps, provided the number of faulty vertices does not exceed n. Finally, we present simulation experiments of ISTs and an application of ISTs in diagnosis on 0-M ₄.     

Fault-free mutually independent Hamiltonian cycles of faulty star graphs

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG _n denote an n-dimensional star network in which f≤n?3 edges may fail accidentally. We show that there exist (n?2?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n∈{3, 4}, and there exist (n?1?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n≥5.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.