There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)[2/3 cos(/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

A simpler minimum spanning tree verification algorithm

The problem considered here is that of determining whether a given spanning tree is a minimal spanning tree. In 1984 Komlós presented an algorithm which required only a linear number of comparisons, but nonlinear overhead to determine which comparisons to make. We simplify his algorithm and give a linear-time procedure for its implementation in the unit cost RAM model. The procedure uses table lookup of a few simple functions, which we precompute in time linear in the size of the tree.     

VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md$\mathit{md}$-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP$\mathit{NP}$-hard.     

A faster distributed protocol for constructing a minimum spanning tree

This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27], where Λ(G) denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253-261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where μ(G,ω) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.     

Algorithm for constrained delaunay triangulation

A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.     

The multi-criteria minimum spanning tree problem based genetic algorithm

Minimum spanning tree (MST) problem is of high importance in network optimization and can be solved efficiently. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problems in the real world, but it is difficult for traditional optimization technique to deal with. In this paper, a non-generational genetic algorithm (GA) for mc-MST is proposed. To keep the population diversity, this paper designs an efficient crossover operator by using dislocation a crossover technique and builds a niche evolution procedure, where a better offspring does not replace the whole or most individuals but replaces the worse ones of the current population. To evaluate the non-generational GA, the solution sets generated by it are compared with solution sets from an improved algorithm for enumerating all Pareto optimal spanning trees. The improved enumeration algorithm is proved to find all Pareto optimal solutions and experimental results show that the non-generational GA is efficient.     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.     

Minimal roughness property of the Delaunay triangulation

A set of scattered data in the plane consists of function values measured on a set of data points in R². A surface model of this set may be obtained by triangulating the set of data points and constructing the Piecewise Linear Interpolating Surface (PLIS) to the given function values. The PLIS is combined of planar triangular facets with vertices at the data points. The roughness measure of a PLIS is the L² norm squared of the gradient of the piecewise linear surface, integrated over the triangulated region and obviously depends on the specific triangulation. In this paper we prove that the Delaunay triangulation of the data points minimizes the roughness measure of a PLIS, for any fixed set of function values. This Theorem connects for the first time, as far as we know, the geometry of the Delaunay triangulation with the properties of the PLIS defined over it.     

An algorithm for geometric minimum spanning trees requiring nearly linear expected time

We describe an algorithm for finding a minimum spanning tree of the weighted complete graph induced by a set ofn points in Euclideand-space. The algorithm requires nearly linear expected time for points that are independently uniformly distributed in the unitd-cube. The first step of the algorithm is the spiral search procedure described by Bentleyet al. [BWY82] for finding a supergraph of the MST that hasO(n) edges. (The constant factor in the bound depends ond.) The next step is that of sorting the edges of the supergraph by weight using a radix distribution, or bucket, sort. These steps require linear expected time. Finally, Kruskal's algorithm is used with the sorted edges, requiringO(n(cn, n)) time in the worst case, withc>6. Since the function (cn, n) grows very slowly, this step requires linear time for all practical purposes. This result improves the previous bestO(n log log*n), and employs a much simpler algorithm. Also, this result demonstrates the robustness of bucket sorting, which requiresO(n) expected time in this case despite the probability dependency between the edge weights.     

Efficient minimum spanning tree construction without Delaunay triangulation

Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.     

A fast distributed approximation algorithm for minimum spanning trees

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $H\,\in\,[1, \Theta({\rm log} n)]We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time ?(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal ?(D(G)) time.     

两维区域三角剖分的新算法

提出一种两维区域三角剖分的新算法,算法首先递归应用求两维点集凸包的Graham扫描法,在原始区域的点集中求出一系列的凸包,同时原始两维区域也被这些凸包划分为多个独立的子区域,然后对相邻两个凸包之间的子区域进行三角剖分,从而实现对整个原始两维区域的三角剖分.和以往得算法相比,提出的算法的时间效率大大提高了,并且在作者参与的军队2110建设项目应用中也体现了良好的效果.     

Complex conforming Delaunay triangulation

A novel algorithm of conforming Delaunay triangulation for curved geometry is presented in the paper.A progress has been made for the problem puzzled Delaunay refinement where curved constraints cannot be accepted as input directly.The algorithm is based on a new sufficient condition for the existence of constraints in triangulation.It requires computing only the intersection between constraints and Voronoi edges or faces instead of the circum-sphere of curved constraint.For the termination of the algorithm...