Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。

Steiner Tree Based Optimal Resource Caching Scheme in Fog Computing

Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.

An Improved MPH-Based Delay-constrained Steiner Tree Algorithm

In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least;if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

G-Tree:基于引力指向技术减少拐弯的Steiner树算法

提出一种基于引力指向技术、以减少拐弯数为目标的最小直角Steiner树构造算法G-Tree.利用一个节点受到其他节点的引力来决定它的移动方向,并采用引力加权以考虑减少拐弯数,生成Steiner树后对拐弯数进行了进一步优化.减少拐弯数有助于在布线阶段减少可能的通孔,从而增强电路的可靠性和可制造性.实验结果表明,G-Tree算法在减少布线树的拐弯数方面有明显的效果.

Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.

Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data

Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.

A Practical Algorithm for the Minimum RectilinearSteiner Tree

An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.

TRANSFORMATIONS FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM AND THE MAXIMUM-WEIGHT CONNECTED SUBGRAPH PROBLEM TO SAP

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.

Algorithms for the Prize-Collecting k-Steiner Tree Problem

In this paper,we study the prize-collecting k-Steiner tree(PCkST) problem.We are given a graph G=(V,E) and an integer k.The graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in R.Excluding a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge cost.We wish to find a feasible solution with minimum total cost.The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F.We present a simple approximation algorithm with the ratio of 5.9672 for the PCkST.This algorithm uses the approximation algorithms for the prize-collecting Steiner tree(PCST) problem and the k-Steiner tree(kST) problem as subroutines.Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

Definition and Algorithms for Reliable Steiner Tree Problem

This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.

“Steiner trees” between cell walls of sisal

Through careful analysis on the cross-section of sisal fibers, it is found that the middle lamellae between the cell walls have clear geometric characteristics: between the cell walls of three neighboring cells, the middle lamellae form a three-way junction with 120° symmetry. If the neighboring three-way junctions are connected, a network of Steiner tree with angular symmetry and topological invariability is formed. If more and more Steiner trees are connected, a network of Steiner rings is generated. In another word, idealized cell walls and the middle lamellae are dominated by the Steiner geometry. This geometry not only depicts the geometric symmetry, the topological invariability and minimal property of the middle lamellae, but also controls the mechanics of sisal fibers.

Algorithms for degree-constrained Euclidean Steiner minimal tree

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.

STEINER MINIMAL TREES FOR ZIGZAG LINES WITH LADDERS

In this paper,Steiner minimal trees for point sets with special structure are studied. These sets consist of zigzag lines and equidistant points lying on them.

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最小树问题,为组合优化中的NP难题,因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格,然后分别介绍两种算法的原理及实现过程,最后通过一系列计算实验,测试了算法的运行性能,获得了较好的效果。

基于Steiner树的层次型无线传感器网络安全组播协议

在基于查询的无线传感器网络中,组播技术的应用可大幅减少传感器节点的能量消耗,延长节点寿命。针对大型无线传感器网络组播协议性能不高,且易遭受攻击等问题,提出了基于Steiner树的层次型无线传感器网络安全组播协议。该协议主要运用Steiner树与分簇网络的思想,将Steiner树的高效性与簇的高扩展性相结合,提高了无线传感器网络组播效率,均衡了网络能量消耗,延长了网络生命周期,并在此基础上加入安全通信机制,以抵御各种网络攻击并确保组播数据的安全性、完整性与可验证性。最后通过理论证明及模拟实验表明本协议适用于大规模无线传感器网络,具有较低能耗及较高安全性。

一种改进的Steiner树启发式算法

最小Steiner树问题是NP完全问题,关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在 MPH算法的基础上,对于经过某些关键节点的短路径优先考虑,提出了KBMPH算法,从而实现更多链路的共享。在随机网络上的仿真结果表明,极大多数情况下,在准Steiner树的网络费用上KBMPH算法优于MPH算法,KBMPH算法的复杂度为)(3nO。

欧氏Steiner最优树的快速算法

针对欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最优树问题,给出了插入算法、递增优化算法、遗传算法等三种快速算法,并在微机上予以实现。经大量实例测试和结果比较,获得了满意的效果。

基于虚拟Steiner树的无线传感器网络组播随机路由协议研究

针对基于树的组播路由协议中组播树鲁棒性不好,扩展能力差的特点,又结合无线传感器网络自身能量、计算、存储能力有限的特点,提出了基于虚拟Steiner树的组播随机路由协议VMRRP(Virtual-steiner-tree based Multicast Random Routing Protocol)。该协议的随机路由思想,使得组播树中源节点到各个组成员节点的路径是动态变化的,与GMP(Geographic Multicast Routing)协议相比,增加了组播树的鲁棒性,也均衡了网络能量,增加了网络生命周期,并通过NS-2仿真试验得到了验证。

基于自适应PSO和混合转换策略的X结构Steiner最小树算法

X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.