关于五个点的Steiner比猜想的一个简单的证明

Ｓｔｅｉｎｅｒ比猜想对任何正整数ｎ成立与否仍待解决，只有ｎ≤５的证明成立，ｎ＝５时有的证明过于繁琐或残缺。本文仍用伸与缩的方法，对ｎ＝５时给出一个真正简单的证明。     

邻接树图是哈密尔顿图猜想的一个等价命题

本文给出了简单图的邻接树图是哈密尔顿图”猜想的等价命题,阐明只需证明该猜想对2－连通图成立即可,另外,我们给出了该猜想一种特殊情形的构造性证明。     

关于Steiner树的一个不等式

本文部分地改进了堵丁柱、黄光明所证明的Gilbert-Pollak关于Steiner树的一个猜想,提出一个新的不等式。     

有关斐波那契三角形猜想的部分证明

有关斐波那契三角形猜想的部分证明张善立（浙江岱山中学３１６２００）对于Ｆｉｂｏｎａｃｃｉ三角形的定义及有关猜想，文［１］，［２］已作了完整的介绍，并已知当ｋ＝１，２及ｎ≤２５时猜想成立．本文对ｋ＝３时的猜想作出证明．定理不存在以为边长的Ｆｉｂｏｎａｃ...     

关于斐波那契三角形猜想的又一结果

关于斐波那契三角形猜想的又一结果纪锋（江苏省南通农业学校２２６０００）文［１］介绍了斐波那契Ｆｉｂｏｎａｃｃｉ）三角形的有关概念，猜想和部分结果，文［２］，［３］又给出了Ｆｉｂｏｎａｃｃｉ三角形猜想的一些结论，这些结论概括起来就是：以（Ｆｎ，Ｆｎ＋ｋ...     

关于Fibonacci三角形的又一结果

关于Ｆｉｂｏｎａｃｃｉ三角形的又一结果许康华（浙江省富阳中学３１１４００）陈计先生在文［１］中介绍了如下猜想：当１≤ｋ＜ｎ时，不存在以（Ｆｎ－ｋ，Ｆｎ，Ｆｎ）为边长的Ｆｉｂｏｎａｃｃｉ三角形．文［２］指出，要证明这个猜想，只需证明不存在以（Ｆ３ｍ，Ｆ...     

随机无穷点集上欧几里德最小扩张树的自包含性

本文证明好的欧氏空间无穷点集上最小扩张树的自包含性．应用上述性质,以及AlexanderK．S．[1]中有关二维Poisson连续渗流的结果,我们给出二维情形AldousD．和SteeleJ．M．[2]之猜想的一个新证明,区别于AlexanderK．S．[3]对上述猜想的排除法证明,我们直接证明它,显然,我们的证明更简单．对Poisson连续渗流,得到其二维临界值相对于Poisson最小扩张树的一个刻画;最后我们给出上述临界值相对于点渗流临界值的一个上下界估计。     

关于连续Fibonacci数的公式

关于连续Ｆｉｂｏｎａｃｃｉ数的公式简超（武汉铁路成人中专４３００１２）设Ｆｎ表示Ｆｉｂｏｎａｃｃｉ数：Ｆ１＝Ｆ２＝１，Ｆｎ＋２＝Ｆｎ＋Ｆｎ＋１，ｎ＝１，２，３，…并约定Ｆ０＝０．本文给出关于连续Ｆｉｂｏｎａｃｃｉ数的几类公式，并证明文［１］的猜想成立...     

一个代数不等式的证明

一个代数不等式的证明４１０１２８湖南农业大学２２５＃陈宽红定理设ｘ，ｙ，ｚ∈Ｒ且ｘ＋ｙ＋ｚ＝０，ｎ∈Ｎ，则这是福建杨学枝老师于１９９４年提出的一个猜想，本文将证明此猜想．证（１）当ｎ＝１，２时，①式显然成立．（２）考察ｎ≥３，ｎ∈Ｎ的情形．１°若ｘ，...     

关于斐波那契三角形猜想的二个结论

关于斐波那契三角形猜想的二个结论江明（江苏省溧阳职业高级中学）陈计先生在文［１］中介绍了斐波那契（Ｆｉｂｏｎａｃｃｉ）三角形的猜想和部分结论：猜想当１≤ｋ＜ｎ时，不存在以（Ｆｎ－ｋ，Ｆｎ，Ｆｎ）为边长的Ｆｉｂｏｎａｃｃｉ三角形．并指出有人已证明了：当...     

Minimum Networks for Four Points in Space

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept — Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W.D. Smith and J.M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.     

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.     

Localization of minimax points

In their proof of Gilbert–Pollak conjecture on Steiner ratio, Du and Hwang (Proceedings 31th FOCS, pp. 76–85 (1990); Algorithmica 7:121–135, 1992) used a result about localization of the minimum points of functions of the type max _y∈Y f(·, y). In this paper, we present a generalization of such a localization in terms of generalized vertices, when we minimize over a compact polyhedron, and Y is a compact set. This is also a strengthening of a result of Du and Pardalos (J. Global Optim. 5:127–129, 1994). We give also a random version of our generalization.     

Optimal Relay Location for Resource-limited Energy-efficient Wireless Communication

In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree by deploying additional relay nodes at specific locations. This optimization problem, known as the Bottleneck Steiner Tree Problem (BSTP), asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. We present a ratio- polynomial time approximation algorithm for BSTP, where is an arbitrary positive number.     

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.     

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Recently, Byrka, Grandoni, Rothvoß and Sanità gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

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.     

Comparison of formulations and a heuristic for packing Steiner trees in a graph

In this paper, we consider the problem of packing Steiner trees in a graph. This problem arises during the global routing phase of circuit layout design. We consider various integer programming formulations and rank them according to lower bounds they provide as LP-relaxations. We discuss a solution procedure to obtain both lower and upper bounds using one of the LP-relaxations. Computational results to test the effectiveness of our procedures are provided.