Minimum Spanning Table and Optimal Expansion of Competence Set

Each directed graph with asymmetric costs defined over its arcs can be represented by a matrix or table, called an expansion table. We explore first the basic properties of cycles and spanning tables of expansion tables, which correspond to the cycles and spanning trees of the directed graph. Then, we derive an algorithm to find a minimum spanning table which corresponds to a minimum spanning tree in the directed graph. Finally, we discuss how to use the algorithm to find the optimal competence set expansion and also discuss related problems.     

The complexity of a minimum reload cost diameter problem

We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].     

Mycielski图的BBC染色

基于图G的Mycielski图M（G）,研究xb（G,TG）与xb（M（G）,T’）之间的关系以及xb（G,TG）与xb（M（G）,T＂）之间的关系,其中Tc为G的生成树,T’,T＂分别为M（G）的两类特殊生成树．并给出当G为二部图,完全图以及Halin图时,Xb（M（G）,T＂）的值．     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Spanning trees with pairwise nonadjacent endvertices

A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

模糊联盟合作对策的平均树解

给出图对策中平均树解的拓展形式, 证明其是满足分支有效性和分支公平性的唯一解. 针对具有模糊联盟的图对策, 提出了一种模糊分配, 即模糊平均树解. 当模糊联盟图对策为完全图对策时, 模糊平均树解等于模糊Shapley值. 最后, 讨论了模糊平均树解与模糊联盟核心之间的关系, 并进行了实例论证.     

Upper and lower bounding procedures for the minimum caterpillar spanning problem

A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions.     

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

Variable neighbourhood search for the minimum labelling Steiner tree problem

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.     

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.     

Minimum congestion spanning trees in bipartite and random graphs

The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n 3 2 , where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n 3 2 .     

Efficient spanning trees

The definition of a shortest spanning tree of a graph is generalized to that of an efficient spanning tree for graphs with vector weights, where the notion of optimality is of the Pareto type. An algorighm for obtaining all efficient spanning trees is presented.     

A self-dual language for graph theory

A symbolic language is developed around the primitive notions of edge and spanning tree, with each spanning tree being interpreted as a binary relation on edges. A sense is considered in which the properties expressible in this language are precisely the self-dual properties of graph theory.     

A Benders decomposition approach for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.This paper describes a new exact method, based on Benders decomposition, for the robust spanning tree problem with interval data. Computational results highlight the efficiency of the new method, which is shown to be very fast on all the benchmarks considered, and in particular on those that were harder to solve for the methods previously known.     

Parity and disparity subgraphs

A parity subgraph of a graph is a spanning subgraph such that the degrees of each vertex have the same parity in both the subgraph and the original graph. Known results include that every graph has an odd number of minimal parity subgraphs. Define a disparity subgraph to be a spanning subgraph such that each vertex has degrees of opposite parities in the subgraph and the original graph. (Only graphs with all even-order components can have disparity subgraphs). Every even-order spanning tree contains both a unique parity subgraph and a unique disparity subgraph. Moreover, every minimal disparity subgraph is shown to be paired by sharing a spanning tree with an odd number of minimal parity subgraphs, and every minimal parity subgraph is similarly paired with either one or an even number of minimal disparity subgraphs.     

The Minimum Stretch Spanning Tree Problem for Typical Graphs

Acta Mathematicae Applicatae Sinica, English Series - With applications in communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the...     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

Confidence regional method of stochastic spanning tree problem

We consider a P model version of stochastic spanning tree problems with random edge costs. Parameters of underling probability distribution of edge costs are unknown and so they are estimated by a confidence region from statistical data. The problem is first transformed into a deterministic equivalent problem with a minimax type objective function and a confidence region of means and variances, since we assume normal distributions with respect to random edge costs. Our model reflects the situation that the maximum possible damage due to an unknown parameter should be minimized. We show the problem can be reduced to the deterministic equivalent problem of another stochastic spanning tree problem, which is already investigated by us. Thus, we can find an optimal spanning tree of the original problem very efficiently by this reduction.