Maximizing the number of spanning trees of networks based on cycle basis representation

In this paper, we consider the problem of finding the graph topology of p vertices and q edges such that the resulting graph contains the maximum number of spanning trees. For any values of p and q, this problem still remains open. Only when q≧ p(p? l)/2 ? [p/2] it has been solved by Shier [4] and, recently, when q = p+1 it has been solved by Wang and Wu [5]. In this paper, we shall formulate this problem into a nonlinear integer program by using the properties of the cycle bases of graphs. And then we shall show that this nonlinear integer program can be easily solved when q = p+ 1 by applying our cycle basis approach. Consequently, we shall solve the nonlinear integer program when q =p + 2. Finally, concluding remarks will be given.     

Maximizing the number of spanning trees of networks based on cycle basis representation

In this paper, we consider the problem of finding the graph topology of p vertices and q edges such that the resulting graph contains the maximum number of spanning trees. For any values of p and q, this problem still remains open. Only when q≧ p(p? l)/2 ? [p/2] it has been solved by Shier [4] and, recently, when q = p + 1 it has been solved by Wang and Wu [5]. In this paper, we shall formulate this problem into a nonlinear integer program by using the properties of the cycle bases of graphs. And then we shall show that this nonlinear integer program can be easily solved when q = p + 1 by applying our cycle basis approach. Consequently, we shall solve the nonlinear integer program when q = p + 2. Finally, concluding remarks will be given.     

字典乘积网络的支撑树计数

支撑树个数是边失效下网络可靠性分析与设计的一个重要性能参考指标,本文利用字典乘积的方法来构建网络,通过这种方法我们很容易由若干特定规模较小网络来构建规模较大的网络,并得到它的一个紧的支撑树计数解析公式,这样的计数公式仅仅依赖于小网络的性能参数,如:结点的度数、小网络的阶数、小网络的支撑树数目.     

The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.     

The number of spanning trees in a new lexicographic product of graphs

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

On the number of spanning trees of circulant graphs

In this paper, we derive a simple formula for the number of spanning trees of the circulant graphs. Some special cases of the circulant graphs are also taken into account.     

Distributed hierarchical search for balanced energy consumption routing spanning trees in wireless sensor networks

We provide a new heuristic method approach to search for degree-balanced and small weight routing spanning trees in a network. The method is a modification of Kruskal’s minimum spanning tree search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum weighted degree, a bigger diameter, and can be used for balanced energy consumption routing in wireless sensor networks (WSN’s). The method can be naturally implemented in parallel or as a simple locally distributed algorithm. Simulations for a realistic case scenario WSN are done based on the transmission energy matrix. The simulation results show that the proposed approach can extend the functional lifetime of a WSN in terms of sensor transmission energy by 3–4 times. We also show that the results can be further improved by using a preliminary clustering of the input network.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

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.     

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.     

Maximizing the number of spanning trees on the (p,p+2) graphs

This paper considers the problem of maximizing the number of spanning trees. A newly established result is the formula and the graph topology for the maximum number of spanning trees among the class of (p, p+2) graph.     

A fast distributed approximation algorithm for minimum spanning trees

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $H\,\in\,[1, \Theta({\rm log} n)]We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time ?(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal ?(D(G)) time.     

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

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.     

An algorithm for geometric minimum spanning trees requiring nearly linear expected time

We describe an algorithm for finding a minimum spanning tree of the weighted complete graph induced by a set ofn points in Euclideand-space. The algorithm requires nearly linear expected time for points that are independently uniformly distributed in the unitd-cube. The first step of the algorithm is the spiral search procedure described by Bentleyet al. [BWY82] for finding a supergraph of the MST that hasO(n) edges. (The constant factor in the bound depends ond.) The next step is that of sorting the edges of the supergraph by weight using a radix distribution, or bucket, sort. These steps require linear expected time. Finally, Kruskal's algorithm is used with the sorted edges, requiringO(n(cn, n)) time in the worst case, withc>6. Since the function (cn, n) grows very slowly, this step requires linear time for all practical purposes. This result improves the previous bestO(n log log*n), and employs a much simpler algorithm. Also, this result demonstrates the robustness of bucket sorting, which requiresO(n) expected time in this case despite the probability dependency between the edge weights.     

Distributed verification of minimum spanning trees

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node “knows” which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (as long as W > (log n)^1+ε for some fixed ε > 0). Both our bounds improve previously known bounds for the problem. For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings. A preliminary version of this work was presented in ACM PODC 2006. A. Korman was supported in part at the Technion by an Aly Kaufman fellowship. S. Kutten was supported in part by a grant from the Israeli Ministry for Science and Technology.     

Optimal parallel verification of minimum spanning trees in logarithmic time

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan. Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.