Parallel construction of optimal independent spanning trees on hypercubes

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. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang, Y.-L. Wang, Y.-H. Leu, Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering 20 (2004) 143–155] studied the problem of constructing k ISTs on k-dimensional hypercube Q_k, and provided a recursive algorithm for their construction (i.e., for constructing k ISTs of Q_k, it needs to build k − 1 ISTs of Q_k−1 in advance). This kind of construction forbids the possibility that the algorithm could be parallelized. In this paper, based on a simple concept called Hamming distance Latin square, we design a new algorithm for generating k ISTs of Q_k. The newly proposed algorithm relies on a simple rule and is easy to be parallelized. As a result, we show that the ISTs we constructed are optimal in the sense that both the heights and the average path length of trees are minimized.     

Optimal Independent Spanning Trees on Odd Graphs

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.     

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.     

Vertex rankings of chordal graphs and weighted trees

In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

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.     

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 ₄.     

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     

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.     

Independent spanning trees on twisted cubes

Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the n independent spanning trees conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for n-connected graphs with n≤4, and they are still open for arbitrary n-connected graph when n≥5. In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the n-dimensional twisted cube TQ_n by providing an O(NlogN) algorithm to construct n vertex-independent spanning trees rooted at any vertex, where N denotes the number of vertices in TQ_n. Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n≥2.     

<Emphasis Type="Italic">k</Emphasis>-Outerplanar Graphs,Planar Duality,and Low Stretch Spanning Trees

Low distortion probabilistic embedding of graphs into approximating trees is an extensively studied topic. Of particular interest is the case where the approximating trees are required to be (subgraph) spanning trees of the given graph (or multigraph), in which case, the focus is usually on the equivalent problem of finding a (single) tree with low average stretch. Among the classes of graphs that received special attention in this context are k-outerplanar graphs (for a fixed k): Chekuri, Gupta, Newman, Rabinovich, and Sinclair show that every k-outerplanar graph can be probabilistically embedded into approximating trees with constant distortion regardless of the size of the graph. The approximating trees in the technique of Chekuri et al. are not necessarily spanning trees, though.     

Optimal parallel algorithms for multiple updates of minimum spanning trees

Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of an efficient algorithm for a single update. However, for efficiency reasons, parallel algorithms for multiple update problems must consider all changes to the underlying graph simultaneously. In this paper we describe parallel algorithms for updating an MST whenk new vertices are inserted or deleted in the underlying graph, when the costs ofk edges are changed, or whenk edge insertions and deletions are performed. For multiple vertex insertion update, our algorithm achieves time and processor bounds ofO(log n·logk) and nk/(logn·logk), respectively, on a CREW parallel random access machine. These bounds are optimal for dense graphs. A novel feature of this algorithm is a transformation of the previous MST andk new vertices to a bipartite graph which enables us to obtain the above-mentioned bounds.     

Survivable network design: the capacitated minimum spanning network problem

We are given an undirected graph G=(V,E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r∈V. In this paper, we consider the capacitated minimum spanning network (CMSN) problem, which asks for a minimum cost spanning network such that the removal of r and its incident edges breaks the network into a number of components (groups), each of which is 2-edge-connected with a total weight of at most k. We show that the CMSN problem is NP-hard, and present a 4-approximation algorithm for graphs satisfying triangle inequality. We also show how to obtain similar approximation results for a related 2-vertex-connected CMSN problem.     

Independent spanning trees on even networks

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. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on even networks, and show that these ISTs are optimal for height and path lengths, and each path in the ISTs has length at most the length of the shortest path+4 in the even network.     

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.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.     

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.     

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.     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.