Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

On Minimum Edge Ranking Spanning Trees

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.     

Bounded-degree spanning tree problems: models and new algorithms

Given a connected graph G, a vertex v of G is said to be a branch vertex if its degree is greater than 2. We consider two problems arising in the context of optical networks:

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d _G (u) + d _G (v) ≥ 9, then G has a spanning eulerian subgraph.     

On the probabilistic min spanning tree Problem

We study a probabilistic optimization model for min spanning tree, where any vertex v _i of the input-graph G(V, E) has some presence probability p _i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any G￠ í GG' \subseteq G is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Backbone colorings for graphs: Tree and path backbones

We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex coloring V → {1,2,…} of G in which the colors assigned to adjacent vertices in H differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of G the number of colors needed for a backbone coloring of G can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(G); for path backbones this factor is roughly . We show that the computational complexity of the problem “Given a graph G, a spanning tree T of G, and an integer ?, is there a backbone coloring for G and T with at most ? colors?” jumps from polynomial to NP‐complete between ? = 4 (easy for all spanning trees) and ? = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Improved Self-Stabilizing Algorithms for L(2, 1)-Labeling Tree Networks

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper—presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria—we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Δ +  2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Δ +  2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

Note on Perfect Forests in Digraphs

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP‐hard, for the three others this problem is polynomial‐time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*

Given a spanning tree T of some graph G, the problem of minimum spanning tree verification is to decide whether T = MST(G). A celebrated result of Komlós shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is e in the MST of T ∪{e}?”, where the tree T is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires Ω(mα(m,n)) time, where α(m,n) is the inverse-Ackermann function and n is the size of the tree. On the other hand, we show that if the weights of T are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time. * A preliminary version of this paper appeared in the proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 155–163. † This work was supported by Texas Advanced Research Program Grant 003658-0029-1999, NSF Grant CCR-9988160, and an MCD Graduate Fellowship.     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

An optimal algorithm for finding depth-first spanning tree on permutation graphs

LetG be a connected graph ofn vertices. The problem of finding a depth-first spanning tree ofG is to find a connected subgraph ofG with then vertices andn − 1 edges by depth-first-search. In this paper, we propose anO(n) time algorithm to solve this problem on permutation graphs.     

Interpolation theorem for the number of end-vertices of spanning trees

The following interpolation theorem is proved: If a graph G contains spanning trees having exactly m and n end-vertices, with m < n, then for every integer k, m < k < n, G contains a spanning tree having exactly k end-vertices. This settles a problem posed by Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.