Hop constrained Steiner trees with multiple root nodes

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches.     

Spanning trees with variable degree bounds

In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed on the edge. We also discuss a particular case that arises in the design of wireless mesh networks (in this variant the degree of the endnodes of each edge depend on the transmission system installed on it as well as on the length of the edge). We propose three classes of models using different sets of variables and compare from a theoretical perspective as well as from a computational point of view, the models and the corresponding linear programming relaxations. The computational results show that some of the proposed models are able to solve to optimality instances with 100 nodes and different scenarios.     

Sizes of the largest clusters for supercritical percolation on random recursive trees

We consider Bernoulli bond‐percolation on a random recursive tree of size , with supercritical parameter for some fixed. We show that with high probability, the largest cluster has size close to whereas the next largest clusters have size of order only and are distributed according to some Poisson random measure. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 29–44, 2014     

Asymptotics of trees with a prescribed degree sequence and applications

Let t be a rooted tree and n_bi(t) the number of nodes in t having i children. The degree sequence of t satisfies , where denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence ; we write for the corresponding distribution. Let be a list of degree sequences indexed by κ corresponding to trees with size . We show that under some simple and natural hypotheses on the trees sampled under converge to the Brownian continuum random tree after normalisation by . Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014     

Exact boundary controllability of nodal profile for quasilinear wave equations in a planar tree‐like network of strings

Based on the theory of semi‐global piecewise C² solutions to 1D quasilinear wave equations, the local exact boundary controllability of nodal profile for quasilinear wave equations in a planar tree‐like network of strings with general topology is obtained by a constructive method. The principles of providing nodal profiles and of choosing and transferring boundary controls are presented, respectively. Copyright © 2013 John Wiley & Sons, Ltd.     

关于Steiner问题的一个注记—连接五点之最小网络的一种寻优方案(英文)

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题.通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案.     

Linear time algorithm for the longest common repeat problem

Given a set of strings U={T₁,T₂,…,T_ℓ}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string of U. We also consider reversed and reverse-complemented repeats as well as normal repeats. We present a linear time algorithm for the longest common repeat problem.     

Some tractable instances of interval data minmax regret problems

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.     

由Abel定理导出的组合恒等式、概率分布及应用

一般的损失分布为伽玛分布、威布尔分布或他们的特例指数分布 .但有些损失分布具有 U形特征 .本文根据二项式定理的另一种拓展形式 ,导出了一类新型组合恒等式 ,并将其推广到多维情形 .由此导出一类新的分布列 .最后给出了该恒等式和分布在图论和质量管理中的应用 .