带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Steiner树问题．设欧氏平面上有一圆，平面上有n个点，所成点集为N，该问题是要在圆周上找一点P，使NU{P}这n 1个点的Steiner树之长度达到最短．本文对干n=2的情形给出解．另一方面，鉴干问题的复杂性为NP-C，作者提出了一个近似解，并证明了近似解的性能比为（3的平方根）／2。     

带机器准备时间的平行机排序问题

研究了带机器准备时间的m台平行机排序问题,设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数m为固定常数的情形下的全多项式时间近似方案(FPTAS).     

三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

λ5-geometry中的Steiner树问题( )

首先研究了λ5-geometry中4个点的Steiner最小树的某些特性,然后证明了对于λ5-geometry中的给定点集P,必有P的一个Steiner最小树,其Stein-er点在P的前2n/3代格点中.     

系列平行图SHMeredith图的关联着色

图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ 2,2)-关联着色.     

系列平行图和Meredith图的关联着色

图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ+2,2)-关联着色.     

相对于Wiener-Hosoya指标的最小树

Wiener-Hosoya指标是由Randic在文[1]中引入的一个指标,旨在揭示分子结构与其化学性质的更进一步的关系.任意给定点数及直径,本文确定了相对于该指标的最小树.进一步地,具有任意给定点数的最小的16个树也得到确定.     

λ_5-geometry中的Steiner树问题(Ⅰ)

本文首先提出了 λ5-geometry中的 Steiner最小树问题 .讨论了 λ5-ge-ometry中的 Steiner最小树的若干性质 ,并给出了给定点数为 3或 4时 Steiner最小树的基本结构 .     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then utilized to yield a fully polynomial approximation scheme.     

An integer programming formulation of the Steiner problem in graphs

A succinct integer linear programming model for the Steiner problem in networks is presented.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Steiner tree problem II: Properties and classes of facets

This is the second part of two papers addressing the study of the facial structure of the Steiner tree polyhedron. In this paper we identify several classes of facet defining inequalities and relate them to special classes of graphs on which the Steiner tree problem is known to be NP-hard.Corresponding author.The author appreciates partial support from National Science Foundation Grants Nos. DSM-8606188 and ECS 8800281.     

The Steiner tree problem I: Formulations,compositions and extension of facets

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.Corresponding author.     

The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches

We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure.     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。