三路树P（m,n,t）是边幼图的证明

[1]中猜测每一树是边幼图,本证明了三路树P（m,n,t)当（i)n,t为偶数且相等,（ii)t=n 1,(iii)n为奇数且t=n 2时为边幼图。     

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)~(n-q-2), n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.     

一类图的亏格

在刘提出的联树模型的基础上,更广泛未必具有对称性的图类的亏格问题可以得到解决．本文中,我们得到了一类具有比较弱对称性的新图类的亏格．作为推论亦得到了完全三部图Kn,n,l（l≥n≥2）的亏格．此处所用方法比已知用来计算图的亏格问题的方法,如电流图等,更直接且可用线性时间算法实现．     

两类三正则图最大亏格的新有效算法

本文借助联树模型给出了一些已知结果的新证明,并证明了图类Pn的上可嵌入性,提供了求强Pn图P*n最大亏格的一个线性算法.     

三路树P(m,n,t)是边幻图的证明

文 [1 ]中猜测每一棵树是边幻图 .本文证明了三路树 P( m,n,t) ,当 ( i) n,t为偶数且相等 ;( ii)t=n+1 ;( iii) n为奇数且 t=n+2时为边幻图 .     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

树的剖分值

图G的刮分值(dissection)是由Randic在1979年引进的-个二维向量(x,y),记为D(G)=(a(G),b(G)).Xu等人证明了在所有阶数n≥5的树中,星图KI,n-1具有最大的a(C)和b(C)值在本文中,我们将对直径为3的n阶树按照剖分值排序,并确定了在直径为4的n阶树中具有最大剖分值的图.     

网络中一类最短支撑树的计算方法

本文在无向赋权图求最短路的Dijkstra算法的基础上,提出了在有向网络图中寻找具有一个枢纽点且与其它各点均有定向联系的最短支撑树的算法,同时还给出了应用该算法的一个计算实例。     

具有完美匹配树的代数连通度的排序

Jason等确定了阶数为n的具有完美匹配树的最大的代数连通度以及相应的极图．本文确定了阶数为n的具有完美匹配树的第二大到第五大的代数连通度以及达到这些数值的图（或图类）．     

固定直径的树的Wiener指数

图G的wiener指数定义为图中所有点对u,v的距离之和∑d（u,v）. 在这篇文章中,我们刻画了在n个顶点直径为d的所有树中具有第三小wiener指数的树的特征以及介绍了得到这类树的wiener指数排序的方法.     

Swap-vertex based neighborhood for Steiner tree problems

Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swap-vertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swap-vertex moves. Additionally, in order to discriminate different swap-vertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swap-vertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.     

A so-called Cluster Benders Decomposition approach for solving two-stage stochastic linear problems

The optimization of stochastic linear problems, via scenario analysis, based on Benders decomposition requires appending feasibility and/or optimality cuts to the master problem until the iterative procedure reaches the optimal solution. The cuts are identified by solving the auxiliary submodels attached to the scenarios. In this work, we propose the algorithm named scenario Cluster Benders Decomposition (CBD) for dealing with the feasibility cut identification in the Benders method for solving large-scale two-stage stochastic linear problems. The scenario tree is decomposed into a set of scenario clusters and tighter feasibility cuts are obtained by solving the auxiliary submodel for each cluster instead of each individual scenario. Then, the scenario cluster based scheme allows to identify tighter feasibility cuts that yield feasible second stage decisions in reasonable computing time. Some computational experience is reported by using CPLEX as the solver of choice for the auxiliary LP submodels at each iteration of the algorithm CBD. The results that are reported show the favorable performance of the new approach over the traditional single scenario based Benders decomposition; it also outperforms the plain use of CPLEX for medium-large and large size instances.     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

Stochastic spanning tree problem

The minimal spanning tree problem has been well studied and until now many efficient algorithms such as [5,6] have been proposed. This paper generalizes it toward a stochastic version, i.e., considers a stochastic spanning tree problem in which edge costs are not constant but random variables and its objective is to find an optimal spanning tree satisfying a certain chance constraint. This problem may be considered as a discrete version of P-model first introduced by Kataoka [4].First it is transformed into its deterministic equivalent problem P. Then, an auxiliary problem P(R) with a positive parameter R is defined. After clarifying close relations between P and P(R), this paper proposes a polynomial order algorithm fully utilizing P(R). Finally, more improvement of the algorithm and applicability of this type algorithm to other discrete stochastic programming problems are discussed.     

Three enhancements for optimization-based bound tightening

Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17–19 % on average. Most importantly, more instances can be solved when using OBBT.     

The 2D‐directed spanning forest is almost surely a tree

We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi‐infinite paths in the DSF. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Expectation transfer between branching processes and random trees

An approach for translating results on expected parameter values from subcritical Galton–Watson branching processes to simply generated random trees under the uniform model is outlined. As an auxiliary technique for asymptotic evaluations, we use Flajolet's and Odlyzko's transfer theorems. Some classical results on random trees are re-derived by the mentioned approach, and some new results are presented. For example, the asymptotic behavior of linearly recursive tree parameters is described and the asymptotic probability of level k to contain exactly one node is determined. © 1993 John Wiley & Sons, Inc.     

关于混合拟似变分包含问题的解的迭代算法

本文对混合拟似变分包含问题提出新的辅助变分不等式,首先证明辅助变分不等式存在唯一解.然后,通过这一辅助形式建立混和拟似变分包含问题解的迭代算法.最后讨论在新的算法下迭代解的收敛性.     

Unification of Filled Function and Tunnelling Function in Global Optimization

In this paper,two auxiliary functions for global optimization are proposed.These two auxiliaryfunctions possess all characters of tunnelling functions and filled functions under certain general assumptions.Thus,they can be considered as the unification of filled function and tunnelling function.Moreover,the processof tunneling or filling for global optimization can be unified as the minimization of such auxiliary functions.Result of numerical experiments shows that such two auxiliary functions are effective.     

两个微分中值定理证明中辅助函数的多种作法

在数学分析中 ,三个微分中值定理极为重要 .在证明 Lagrange中值定理和 Cauchy中值定理时 ,都少不了作辅助函数 ,各种版本的《数学分析》或《高等数学》书本中 ,都只给出了一种形式的辅助函数 .为了扩展思路 ,给出了多种形式的辅助函数 ,并得出了一般形式 .