关于赋权树的谱半径的精确上界

The spectrum of weighted graphs are often used to solve the problems in the design of networks and electronic circuits. In this paper, we derive the sharp upper bound of spectral radius of all weighted trees on given order and edge independence number, and obtain all such trees that their spectral radius reach the upper bound.     

An efficient algorithm for the Steiner Tree Problem with revenue,bottleneck and hop objective functions

This paper considers a tricriteria Steiner Tree Problem arising in the design of telecommunication networks. The objective functions consist of maximizing the revenue and of minimizing the maximal distance between each pair of interconnected nodes, as well as the maximal number of arcs between the root and each node. A polynomial algorithm is developed for the generation of a minimal complete set of Pareto-optimal Steiner trees. Optimality proofs are given and computational experience on a set of randomly generated problems is reported.     

Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

Graphs with only caterpillars as spanning trees

A connected graph G is caterpillar-pure if each spanning tree of G is a caterpillar. The caterpillar-pure graphs are fully characterized. Loosely speaking they are strings or necklaces of so-called pearls, except for a number of small exceptional cases. An upper bound for the number of edges in terms of the order is given for caterpillar-pure graphs, and those which attain the upper bound are characterized.     

递归树的若干枚举特征

递归树由Meir和Moon定义作非平面增长树的一种，且所有节点出度都是允许的．本文首先在n个节点的递归树集合和n-1个元素的排列之间建立一个新的──对应，这个对应能同时给出树叶子和排列中的路段之间的对应和树叶子数和排列中的路段数之间的密切关系．同时还研究递归树的各种枚举特征，诸如节点的分类枚举（内节点和叶子节点、偶节点和奇节点，具不同出度的节点）和通路长度枚举（接各种节点分类）．     

An involution on increasing trees

We introduce a method to construct bijections on increasing trees. Using this method, we construct an involution on increasing trees, from which we obtain the equidistribution of the statistics ‘number of odd vertices’ and ‘number of even vertices at odd levels’. As an application, we deduce that the expected value of the number of even vertices is twice the expected value of the number of odd vertices in a random recursive tree of given size.     

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of vertices. The complexity of finding a spanning tree of minimum stabbing number is one of the original 30 questions on “The Open Problems Project” list of outstanding problems in computational geometry by Demaine, Mitchell, and O’Rourke. We show -hardness of stabbing problems by means of a general proof technique. For matchings, this also implies a nontrivial lower bound on the approximability. On the positive side, we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the corresponding linear programming relaxation we obtain polynomial-time lower bounds and show that there always is an optimal fractional solution that contains an edge of at least constant weight. We conjecture that the resulting iterated rounding scheme constitutes a constant-factor approximation algorithm. An extended abstract appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms [11]. M.E. Lübbecke visits to Kingston and Stony Brook were supported by a DFG travel grant. H. Meijer partially supported by NSERC while visiting Braunschweig in 2002.     

The Splits in the Neighborhood of a Tree

A phylogenetic tree represents historical evolutionary relationships between different species or organisms. The space of possible phylogenetic trees is both complex and exponentially large. Here we study combinatorial features of neighbourhoods within this space, with respect to four standard tree metrics. We focus on the splits of a tree: the bipartitions induced by removing a single edge from the tree. We characterize those splits appearing in trees that are within a given distance of the original tree, demonstrating close connections between these splits, the Whitney number of a tree, and the binary characters with a given parsimony length.AMS Subject Classification: 68R10, 05C05, 68Q25, 92D15.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

The distance spectral radius of trees

The unique graphs with maximum distance spectral radius among trees with given number of vertices of maximum degree and among homeomorphically irreducible trees, respectively, are determined.     

Chip-Firing and the Critical Group of a Graph

A variant of the chip-firing game on a graph is defined. It is shown that the set of configurations that are stable and recurrent for this game can be given the structure of an abelian group, and that the order of the group is equal to the tree number of the graph. In certain cases the game can be used to illuminate the structure of the group.     

外平面图的对策色数

本文讨论了图的色对策 ,给出了外平面图的几个性质 ,并且利用性质证明了外平面图的对策色数至多是 6     

A more efficient algorithm for MPR problems in phylogeny

A discrete optimization problem of assigning linearly ordered character-states to the hypothetical ancestors of an evolutionary tree under the principle of maximum parsimony has been discussed. Under the transformation relation of linearly ordered character-states, Farris (1970) and Swofford and Maddison (1987) have dealt with the problem on completely bifurcating phylogenetic trees and presented a solution. Hanazawa et al. (1995) have mathematically formulated the problem with its generalization to any tree and called it the MPR (most-parsimonious reconstruction) problem. Then they have presented clear algorithms for the MPR problem and the related problems. We present a more efficient algorithm for one of the problems, the problem of obtaining the MPR sets. The complexity of the previous algorithm for this problem is O(n²) for the number n of nodes in a given tree, but that of the new algorithm is O(n).     

Constrained Inverse Minimum Spanning Tree Problems under the Bottleneck-Type Hamming Distance

In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the weights of edges can be modified only within given intervals. We further consider the constrained case in which the total modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover problems. This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02).     

Locating flow-capturing units on a network with multi-counting and diminishing returns to scale

In the paper we consider the problem of locating flow-capturing units (facilities) on a transportation network, where the level of consuming service by customers depends on the number of facilities that they encounter on their pre-planned tour (the effect of multi-counting). Two location problems are considered: Problem 1 — minimizing the number of facilities required to ensure the maximal level of consumption, and Problem 2 — maximizing the total consumption given a restriction on the number of facilities. Both problems are NP-hard on general networks. Integer programming formulations of the problems are given. For Problem 2, a heuristic with worst-case analysis is presented. It is shown that Problem 2 is NP-hard even on a tree (and even without multi-counting). For Problem 1 on a tree a polynomial algorithm is presented. If it is required additionally that at most one facility can be located at each node and locations are restricted to nodes, then both problems are NP-hard on trees.     

A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

Bi-Objective Median Subtree Location Problems

A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {V–v}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.     

Existential monadic second order logic on random rooted trees

We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).     

树的第二个最大特征值

本文得到了边独立数为n且阶为2n+2的树的第二个最大特征值的精确上界,且给出了达到上界的所有的极树.     

Clustering Methods in Microarrays

Summary DCT Given a finite set of points in an Euclidean space the \emph{spanning tree} is a tree of minimal length having the given points as vertices. The length of the tree is the sum of the distances of all connected point pairs of the tree. The clustering tree with a given length of a given finite set of points is the spanning tree of an appropriately chosen other set of points approximating the given set of points with minimal sum of square distances among all spanning trees with the given length. DCM A matrix of real numbers is said to be column monotone orderable if there exists an ordering of columns of the matrix such that all rows of the matrix become monotone after ordering. The {\emph{monotone sum of squares of a matrix}} is the minimum of sum of squares of differences of the elements of the matrix and a column monotone orderable matrix where the minimum is taken on the set of all column monotone orderable matrices. Decomposition clusters of monotone orderings of a matrix is a clustering ofthe rows of the matrix into given number of clusters such that thesum of monotone sum of squares of the matrices formed by the rowsof the same cluster is minimal.DCP A matrix of real numbers is said to be column partitionable if there exists a partition of the columns such that the elements belonging to the same subset of the partition are equal in each row. Given a partition of the columns of a matrix the partition sum of squares of the matrix is the minimum of the sum of square of differences of the elements of the matrix and a column partitionable matrix where the minimum is taken on the set of all column partitionable matrices. Decomposition of the rows of a matrix into clusters of partitions is the minimization of the corresponding partition sum of squares given the number of clusters and the sizes of the subsets of the partitions.