A simple proof of Hwang's theorem for rectilinear Steiner minimal trees

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: LetS be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree forS has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight linel, and the tree edges incident to the Steiner points onl appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees.     

A decomposition theorem on Euclidean Steiner minimal trees

The Euclidean Steiner minimal tree problem is known to be an NP-complete problem and current alogorithms cannot solve problems with more than 30 points. Thus decomposition theorems can be very helpful in extending the boundary of workable problems. There have been only two known decomposition theorems in the literature. This paper provides a 50% increase in the reservoir of decomposition theorems.     

A short proof of a martingale representation result

Using the Ito differentiation rule, the properties of stochastic flows and the unique decomposition of special seminartingales, the integrand in a stochastic integral is quickly identified.     

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 minimal trees for regular polygons

Fifty years ago Jarnik and Kössler showed that a Steiner minimal tree for the vertices of a regularn-gon contains Steiner points for 3 n5 and contains no Steiner point forn=6 andn13. We complete the story by showing that the case for 7n12 is the same asn13. We also show that the set ofn equally spaced points yields the longest Steiner minimal tree among all sets ofn cocircular points on a given circle.     

Steiner minimal trees on sets of four points

LetS = {A, B, C, D} consist of the four corner points of a convex quadrilateral where diagonals [A, C] and [B, D] intersect at the pointO. There are two possible full Steiner trees forS, theAB-CD tree hasA andB adjacent to one Steiner point, andC andD to another; theAD-BC tree hasA andD adjacent to one Steiner point, andB andC to another. Pollak proved that if both full Steiner trees exist, then theAB-CD (AD-BC) tree is the Steiner minimal tree if AOD>3 (<) 90°, and both are Steiner minimal trees if AOD=90°. While the theorem has been crucially used in obtaining results on Steiner minimal trees in general, its applicability is sometimes restricted because of the condition that both full Steiner trees must exist. In this paper we remove this obstacle by showing: (i) Necessary and sufficient conditions for the existence of either full Steiner tree forS. (ii) If AOD90°, then theAB-CD tree is the SMT even if theAD-BC tree does not exist. (iii) If AOD<90° but theAD-BC tree does not exist, then theAB-CD tree cannot be ruled out as a Steiner minimal tree, though under certain broad conditions it can.     

Steiner minimal trees for bar waves

A Steiner minimal tree (SMT) for a set of pointsP in the plane is a shortest network interconnectingP. The construction of a SMT for a general setP is known to be anNP-complete problem. Recently, SMTs have been constructed for special setsP such as ladders, splitting trees, zigzag lines and co-circular points. In this paper we study SMTs for a wide class of point-sets called mild bar wave. We show that a SMT for a mild bar wave must assume a special form, thus the number of trees needed to be inspected is greatly reduced. Furthermore if a mild bar wave is also a mild rectangular wave, then we produce a Steiner tree constructible in linear time whose length can exceed that of a SMT by an amount bounded by the difference in heights of the two endpoints of the rectangular wave, thus independent of the number of points. When a rectangular wave satisfies some other conditions (including ladders as special cases), then the Steiner tree we produced is indeed a SMT.     

A short zero-one law proof of a result of Abian

Summary In this note a new and very short zero-one law proof of the following theorem of Abian is presented. The subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use a given basis element of a prescribed Hamel basis, has outer Lebesgue measure one and inner measure zero.Let {a, b, c, ...} be a Hamel basis for the real numbers. LetA be the subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use the basis elementa. Sierpinski [4, p. 108] has shown thatA is nonmeasurable in the sense of Lebesgue. Abian [1] has improved Sierpinski's result by showing thatm* (A), the outer measure ofA, is one and thatm _* (A), the inner measure ofA, is zero. In this note a very short proof, using a zero-one law, of Abian's result will be presented.The following zero-one law is an immediate consequence of the Lebesgue Density Theorem [2, p. 290].     

带梯子的曲折线上的最短树问题

Abstract. 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.     

A new proof of a theorem of Graham and Pollak

A simple matrix proof is supplied for the statement that a complete graph on n vertices cannot be partitioned into n ? 2 complete bipartite graphs.     

A combinatorial proof of a result of hetyei and reiner on Foata-Strehl-type permutation trees

We give a combinatorial proof of the known result that there are exactlyn!/3 permutations of lengthn in the minmax tree representation of which theith node is a leaf. This paper was written while the author was a one-term visitor at Mathematical Sciences Research Institute in Spring 1997. This visit was supported by an MIT Applied Mathematics Fellowship.     

Bifurcations of Steiner minimal trees and minimal fillings for non-convex four-point boundaries and Steiner subratio for the Euclidean plane

Bifurcation diagrams for topologies of Steiner minimal trees and minimal fillings for nonconvex four-point boundaries in the Euclidean plane are constructed. Using this result, the four-pointed Steiner subratio of the Euclidean plane is obtained. All configurations which it is attained at are found.     

Steiner minimal trees for three points with one convex polygonal obstacle

The problem of constructing Steiner minimal trees in the Euclidean plane is NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexityO(n), wheren is the number of extreme points on the obstacle. As an extension to the underlying algorithm, if the obstacle is appropriately preprocessed inO(n) time, we can solve any problem instance with three arbitrary terminal points and the preprocessed convex polygonal obstacle inO(logn) time. We believe that the three terminal points algorithm will play a critical role in the development of heuristics for problem instances with arbitrarily many terminal points and obstacles.     

A partition-based relaxation for Steiner trees

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals \({R\subseteq V}\) , and non-negative costs c _e for all edges \({e \in E}\) . Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices \({V \backslash R}\) are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of \({1+\frac{\ln 3}{2}\approx 1.55}\) . The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2?2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky’s algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of \({G \backslash R}\) has at most b vertices. We show that Robins’ and Zelikovsky’s algorithm has an approximation ratio better than \({1+\frac{\ln 3}{2}}\) for such instances, and we prove that the integrality gap of our LP is between \({\frac{8}{7}}\) and \({\frac{2b+1}{b+1}}\) .     

A short proof of a theorem on Hamiltonian graphs

In this note, we give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that $ d(u)+d(v)+d(w) \geq n + \mid N(u) \cap N(v) \cap N(w) \mid $ for any independent set {u, v, w}, then G is hamiltonian. © 1996 John Wiley & Sons Inc.     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.