A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

Two new criteria for finding Steiner hulls in Steiner tree problems

The Steiner tree problem considered in this paper is that of finding a network of minimum length connecting a given setK of terminals in a regionR of the Euclidean plane. ASteiner hull forK inR is any subregion ofR known to contain a Steiner tree forK inR. Two new criteria are given for finding Steiner hulls—one for the Steiner tree problem on plane graphs and one for the rectilinear Steiner tree problem—which strengthen known polynomial-time methods of finding Steiner hulls.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0140. Reproduction in whole or part is permitted for any purpose of the United States Government.     

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题,由于该问题的搜索空间与元胞自动机的结构相似,设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明,该算法要比最小生成树平均改进15%,优于多数已有的基于最小生成树的近似算法,验证了算法的实用性。     

A practical algorithm for the minimum rectilinear steiner tree

An O(n^2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed.The approximation ratio of the algorithm is strictly less than 1.5.The computing performances show the costs of the spanning trees produced by the algorithm are only 0.8% away from the optimal ones.     

A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem

We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q.$Q.$ We present a lower bound and a genetic algorithm for the PCSTP. The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%.     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

New primal–dual algorithms for Steiner tree problems

We present new primal–dual algorithms for several network design problems. The problems considered are the generalized Steiner tree problem (GST), the directed Steiner tree problem (DST), and the set cover problem (SC) which is a subcase of DST. All our problems are NP-hard; so we are interested in their approximation algorithms. First, we give an algorithm for DST which is based on the traditional approach of designing primal–dual approximation algorithms. We show that the approximation factor of the algorithm is k, where k is the number of terminals, in the case when the problem is restricted to quasi-bipartite graphs. We also give pathologically bad examples for the algorithm performance. To overcome the problems exposed by the bad examples, we design a new framework for primal–dual algorithms which can be applied to all of our problems. The main feature of the new approach is that, unlike the traditional primal–dual algorithms, it keeps the dual solution in the interior of the dual feasible region. The new approach allows us to avoid including too many arcs in the solution, and thus achieves a smaller-cost solution. Our computational results show that the interior-point version of the primal–dual most of the time performs better than the original primal–dual method.     

Co-evolutionary algorithms to solve hierarchized Steiner tree problems in telecommunication networks

This study investigates a hierarchized Steiner tree problem in telecommunication networks. In such networks, users must be connected to capacitated hubs. Additionally, selected hubs must be connected to each other and to extra hubs, if necessary, by considering the latency of the resultant network. A connection between hubs can be considered to be a Steiner tree. This Steiner tree problem is modeled as a bi-level mathematical programming problem that considers two decision levels. In the upper-level, the allocation of users to hubs is performed to minimize the total network connection cost. The lower-level minimizes the user latency concerning the information that flows through the capacitated hubs. Further, two co-evolutionary schemes are developed to solve this bi-level model. The first scheme is an individual–population approach, whereas the second scheme is the traditional population–population approach. The first proposed algorithm exploits the structure of the problem by employing parallel computing in one of the populations. Numerical results depict the effectiveness of the proposed algorithms when the lower-level problem cannot be optimally solved efficiently. Furthermore, the advantages of the proposed schemes over an evolutionary one are exhibited. Finally, the hybridization of both co-evolutionary schemes is implemented to improve the semi-feasible solutions obtained by the second scheme, showing its effectiveness to solve the problem.     

节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

A test of randomness based on the minimal spanning tree

We present a test of randomness based on the edge length distribution of the Minimal Spanning Tree.     

基于模拟植物生长算法的求解MCCS问题的研究

为了降低耗能和减少花费,提出了对无线传感网络设计中的最小连通集合划分的方法.采用对网络进行Voronoi划分成近似覆盖集合,对不满足连通的情况采用一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通的方法.通过对算法的时间复杂度分析及算例实验,验证了该算法不但可获得最优解,同时精度和性能也有提高,明显优于其它方法.     

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

Given an underlying communication network represented as an edge-weighted graph G=(V,E), a source node sV, a set of destination nodes DV, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1.55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3.4713. In comparison, the previously best ratio was .     

A simple method to derive minimal cut sets for a non-coherent fault tree

Minimal cut sets (or prime implicants: minimal combinations of basic event conditions leading to system failure) are important information for reliability/safety analysis and design. To obtain minimal cut sets for general non-coherent fault trees, including negative basic events or multi-valued basic events, a special procedure such as the consensus rule must be applied to the results obtained by logical operations for coherent fault trees, which will require more steps and time. This paper proposes a simple method for a non-coherent fault tree, whose top event is represented as an AND combination of monotonic sub-trees. A "monotonic" sub-tree means that it does not have both positive and negative representations for each basic event. It is proven that minimal cut sets can be obtained by a conventional method for coherent fault trees. An illustrative example of a simple event tree analysis shows the detail and characteristics of the proposed method.     

A Distributed Algorithm for Determining Minimal Covers of Acyclic Database Schemes

Acyclic databases possess several desirable properties for their design and use.A distributed algorithm is proposed for determining a minimal cover of an alpha-,beta-,gamma-,or Berge-acyclic database scheme over a set of attributes in a distributed environment.     

A least squares algorithm for fitting an ultrametric tree to a dissimilarity matrix

A least squares algorithm for fitting an ultrametric tree to a dissimilarity matrix is developed. The algorithm is evaluated in a Monte Carlo study in which error-perturbed randomly generated ultrametric distances were analyzed. Finally, an illustrative application is presented.     

最小耗费生成树剔除算法及其正确性证明

文章提出了一种新的最小耗费生成树的算法，并对其正确性进行了证明。该算法通过从原图中逐步别除边来形成生成树，特别适用于当原图中边数较少(相对于顶点数)，或原图规模不大的情形。     

A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets

A simple O(n log n) algorithm is presented for computing the maximum Euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity reduces to O(n).