Gradient-constrained minimum networks. I. Fundamentals

In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value m. A gradient-constrained minimum Steiner tree T is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than m. We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in T is either three or four. If the edges in T are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to m, then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

The Steiner ratio conjecture for cocircular points

A Steiner minimal treeS is a network of shortest possible length connecting a set ofn points in the plane. LetT be a shortest tree connecting then points but with vertices only at these points.T is called a minimal spanning tree. The Steiner ratio conjecture is that the length ofS divided by the length ofT is at least 3/2. In this paper we use a variational approach to show that if then points lie on a circle, then the Steiner ratio conjecture holds.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

The minimum degree of Ramsey‐minimal graphs

We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ? G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(K_k) = (k ? 1)² and s(K_a,b) = 2 min(a,b) ? 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Tree inclusions in windows and slices

A labelled tree P is an embedded subtree of a labelled tree T if P can be obtained by deleting some nodes from T: if a node v is deleted, all edges adjacent to v are also deleted and replaced by edges going from the parent of v (if it exists) to the children of v. Deciding whether P is an embedded subtree of T is known to be NP-complete. Given two trees (a target T and a pattern P) and a natural number w, we address two problems: 1) counting the number of windows of T having height exactly w and containing the pattern P as an embedded subtree, and 2) counting the number of slices of T having height exactly w and containing the pattern P as an embedded subtree. Our algorithms run in time O(|T|(w − h(P)+2)^4|P|), where |T| (respectively, |P|) is the size of T (respectively, P), and h(P) is the height of P. Bibliography: 10 titles. Dedicated to Yu. Matiyasevich on the occasion of his 60th birthday. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 3–53.     

Hyperbolic rank and subexponential corank of metric spaces

We introduce a new quasi-isometry invariant corank X of a metric space X called subexponential corank. A metric space X has subexponential corank k if roughly speaking there exists a continuous map , T is a topological space, such that for each the set g ^-1(t) has subexponential growth rate in X and the topological dimension dimT = k is minimal among all such maps. Our main result is the inequality for a large class of metric spaces X including all locally compact Hadamard spaces, where rank _h X is the maximal topological dimension of among all CAT(—1) spaces Y quasi-isometrically embedded into X (the notion introduced by M. Gromov in a slightly stronger form). This proves several properties of rank _h conjectured by Gromov, in particular, that any Riemannian symmetric space X of noncompact type possesses no quasi-isometric embedding of the standard hyperbolic space H ⁿ with . Submitted: February 2001, Revised: October 2001.     

Edge-colorings of cubic graphs with elements of point-transitive Steiner triple systems

A cubic graph G is S-edge-colorable for a Steiner triple system S if its edges can be colored with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. We show that a cubic graph is S-edge-colorable for every non-trivial affine Steiner triple system S unless it contains a well-defined obstacle called a bipartite end. In addition, we show that all cubic graphs are S-edge-colorable for every non-projective non-affine point-transitive Steiner triple system S.     

Approximations for two variants of the Steiner tree problem in the Euclidean plane {\mathbb{R}^2}

Given n terminals in the Euclidean plane and a positive constant l, find a Steiner tree T interconnecting all terminals with the minimum total cost of Steiner points and a specific material used to construct all edges in T such that the Euclidean length of each edge in T is no more than l. In this paper, according to the cost b of each Steiner point and the different costs of some specific materials with the different lengths, we study two variants of the Steiner tree problem in the Euclidean plane as follows: (1) If a specific material to construct all edges in such a Steiner tree has its infinite length and the cost of per unit length of such a specific material used is c ₁, the objective is to minimize the total cost of the Steiner points and such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_1+ c_1 \cdot \sum_{e \in T} w(e)\}}$ , where T is a Steiner tree constructed, k ₁ is the number of Steiner points and w(e) is the length of part cut from such a specific material to construct edge e in T, and we call this version as the minimum-cost Steiner points and edges problem (MCSPE, for short). (2) If a specific material to construct all edges in such a Steiner tree has its finite length L (l ≤ L) and the cost of per piece of such a specific material used is c ₂, the objective is to minimize the total cost of the Steiner points and the pieces of such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_2+ c_2 \cdot k_3\}}$ , where T is a Steiner tree constructed, k ₂ is the number of Steiner points in T and k ₃ is the number of pieces of such a specific material used, and we call this version as the minimum-cost Steiner points and pieces of specific material problem (MCSPPSM, for short). These two variants of the Steiner tree problem are NP-hard with some applications in VLSI design, WDM optical networks and wireless communications. In this paper, we first design an approximation algorithm with performance ratio 3 for the MCSPE problem, and then present two approximation algorithms with performance ratios 4 and 3.236 for the MCSPPSM problem, respectively.     

On conservative and supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic.     

Complements of Intersections in Constructive Mathematics

We examine, from a constructive perspective, the relation between the complements of S, T, and S ∩ T in X, where X is either a metric space or a normed linear space. The fundamental question addressed is: If x is distinct from each element of S ∩ T, if s ? S, and if t ? T, is x distinct from s or from t? Although the classical answer to this question is trivially affirmative, constructive answers involve Markov's principle and the completeness of metric spaces. Mathematics Subject Classification: 03F65, 46S30.     

Certain Contact Metrics as Ricci Almost Solitons

We show that if a compact K-contact metric is a gradient Ricci almost soliton, then it is isometric to a unit sphere S ²ⁿ⁺¹. Next, we prove that if the metric of a non-Sasakian (κ, μ)-contact metric is a gradient Ricci almost soliton, then in dimension 3 it is flat and in higher dimensions it is locally isometric to E ⁿ⁺¹ ×  S ⁿ (4). Finally, a couple of results on contact metric manifolds whose metric is a Ricci almost soliton and the potential vector field is point wise collinear with the Reeb vector field of the contact metric structure were obtained.     

The steiner minimal network for convex configurations

SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.     

Uniqueness Theorems for CR Functions

Let M be a CR manifold embedded in ?^s of arbitrary codimension. M is called generic if the complex hull of the tangent space in all points of M is the whole ?^s. M is minimal (in sense of Tumanov) in p ? M if there does not exist any CR submanifold of M passing through p with the same CR dimension as M but of smaller dimension. Let M be generic and minimal in some point p ? M and N be a generic submanifold of M passing through p. We prove that a continuous CR function on M vanishes identically in some neigbourhood of p if its restriction to N either vanishes in p faster then some function with non-integrable logarithm or it vanishes on a subset of N of positive measure.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

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.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.