Graham's problem on shortest networks for points on a circle

Suppose a configurationX consists ofn points lying on a circle of radiusr. If at most one of the edges joining neighboring points has length strictly greater thanr, then the Steiner treeS consists of all these edges with a longest edge removed. In order to showS is, in fact, just the minimal spanning treeT, a variational approach is used to show the Steiner ratio for this configuration is at least one and equals one only ifS andT coincide. The variational approach greatly reduces the number of possible Steiner trees that need to be considered.     

Monochromatic geometric k-factors for bicolored point sets with auxiliary points

Given a bicolored point set S, it is not always possible to construct a monochromatic geometric planar k-factor of S. We consider the problem of finding such a k-factor of S by using auxiliary points. Two types are considered: white points whose position is fixed, and Steiner points which have no fixed position. Our approach provides algorithms for constructing those k-factors, and gives bounds on the number of auxiliary points needed to draw a monochromatic geometric planar k-factor of S.     

On resol vability of Steine r systems S( v = 2m, 4, 3) of rank r ≤ v − m + 1 o ve r $$\mathbb{F}_2 $$

Two new constructions of Steiner quadruple systems S(v, 4, 3) are given. Both preserve resolvability of the original Steiner system and make it possible to control the rank of the resulting system. It is proved that any Steiner system S(v = 2 ^m , 4, 3) of rank r ≤ v ? m + 1 over F₂ is resolvable and that all systems of this rank can be constructed in this way. Thus, we find the number of all different Steiner systems of rank r = v ? m + 1.     

Steiner triple systems S(2 m ? 1, 3, 2) of rank 2 m ? m+ 1 over \mathbb{F}_2

Steiner systems S(2 ^m ? 1, 3, 2) of rank 2 ^m ? m+1 over the field $\mathbb{F}_2$ are considered. A new recursive method for constructing Steiner triple systems of an arbitrary rank is proposed. The number of all Steiner systems of rank 2 ^m ? m+1 is obtained. Moreover, it is shown that all Steiner triple systems S(2 ^m ? 1, 3, 2) of rank r ?? 2 ^m ? m+1 are derived, i.e., can be completed to Steiner quadruple systems S(2 ^m , 4, 3). It is also proved that all such Steiner triple systems are Hamming; i.e., any Steiner triple system S(2 ^m ? 1, 3, 2) of rank r ?? 2 ^m ? m + 1 over the field $\mathbb{F}_2$ occurs as the set of words of weight 3 of a binary nonlinear perfect code of length 2 ^m ?1.     

On one transformation of Steiner quadruple systems <Emphasis Type="Italic">S</Emphasis>(<Emphasis Type="Italic">υ</Emphasis>, 4, 3)

A transformation of Steiner quadruple systems S(υ, 4, 3) is introduced. For a given system, it allows to construct new systems of the same order, which can be nonisomorphic to the given one. The structure of Steiner systems S(υ, 4, 3) is considered. There are two different types of such systems, namely, induced and singular systems. Induced systems of 2-rank r can be constructed by the introduced transformation of Steiner systems of 2-rank r − 1 or less. A sufficient condition for a Steiner system S(υ, 4, 3) to be induced is obtained.     

A faster approximation algorithm for the Steiner problem in graphs

Summary We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1–1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(¦E¦log¦V¦) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(¦S¦¦V¦²), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T.J. Watson Research Center.On leave from: Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6380, D-7500 Karlsruhe, Federal Republic of Germany     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane

We study a bottleneck Steiner tree problem: given a set P={p₁,p₂,…,p_n} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem.     

Vasil’ev codes of length n = 2m and doubling of Steiner systems S(n, 4, 3) of a given rank

Extended binary perfect nonlinear Vasil’ev codes of length n = 2^m and Steiner systems S(n, 4, 3) of rank n-m over F ₂ are studied. The generalized concatenated construction of Vasil’ev codes induces a variant of the doubling construction for Steiner systems S(n, 4, 3) of an arbitrary rank r over F ₂. We prove that any Steiner system S(n = 2^m, 4, 3) of rank n-m can be obtained by this doubling construction and is formed by codewords of weight 4 of these Vasil’ev codes. The length 16 is studied in detail. Orders of the full automorphism groups of all 12 nonequivalent Vasil’ev codes of length 16 are found. There are exactly 15 nonisomorphic systems S(16, 4, 3) of rank 12 over F ₂, and they can be obtained from codewords of weight 4 of the extended Vasil’ev codes. Orders of the automorphism groups of all these Steiner systems are found.     

Approximation Algorithms for Intersection Graphs

We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.     

Transforming spanning trees and pseudo-triangulations

Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T^′ of TS are adjacent if T intersects T^′ only in points of S or in common edges. We prove that the diameter of TS is O(logk), where k denotes the number of convex layers of S. Based on this result, we show that the flip graph PS of pseudo-triangulations of S (where two pseudo-triangulations are adjacent if they differ in exactly one edge—either by replacement or by removal) has a diameter of O(nlogk). This sharpens a known O(nlogn) bound. Let be the induced subgraph of pointed pseudo-triangulations of PS. We present an example showing that the distance between two nodes in is strictly larger than the distance between the corresponding nodes in PS.     

Two probabilistic results on rectilinear steiner trees

In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to β√N for some constant β (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants β. In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN.     

Expansion of Linear Steiner Trees

A Steiner tree T on a given set of points A is called linear if all Steiner points, including those collapsing into their adjacent given points, lie on one path referred to as its trunk. Suppose A is a simple polygonal line. Roughly speaking, T is similar to A if its trunk turns right or left when A does. In this paper we prove that A can be expanded to another polygonal line, and T can be constructed in linear time using this expansion method. Received January 15, 1995; revised November 19, 1995, and February 3, 1996.     

The General Steiner Tree-Star problem

The Steiner tree problem is defined as follows—given a graph G=(V,E) and a subset X⊂V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a “switch” cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V?X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.     

Biased Range Trees

A?data structure, called a biased range tree, is presented that preprocesses a set S of n points in ?² and a query distribution D for 2-sided orthogonal range counting queries (a.k.a. dominance counting queries). The expected query time for this data structure, when queries are drawn according to?D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are? O(nlog?n).     

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

Given an n-node, undirected and 2-edge-connected graph G=(V,E) with positive real weights on its m edges, given a set of k source nodes S?V, and given a spanning tree T of G, the routing cost from S of T is the sum of the distances in T from every source s∈S to all the other nodes of G. If an edge e of T undergoes a transient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replace e by means of a swap edge, i.e., an edge in G reconnecting the two subtrees of T induced by the removal of e. Then, a best swap edge for e is a swap edge which minimizes the routing cost from S of the tree obtained after the swapping. As a natural extension, the all-best swap edges problem is that of finding a best swap edge for every edge of T, and this has been recently solved in O(mn) time and linear space. In this paper, we focus our attention on the relevant cases in which k=O(1) and k=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an $\widetilde{O}(m)$ time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input tree T has a routing cost from V which is a constant-factor away from that of a minimum routing-cost spanning tree (whose computation is a problem known to be in APX), and if in addition nodes in T enjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost from V which is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.     

Planar tree transformation: Results and counterexample

We consider the problem of planar spanning tree transformation in a two-dimensional plane. Given two planar trees T₁ and T₂ drawn on a set S of n points in general position in the plane, the problem is to transform T₁ into T₂ by a sequence of simple changes called edge-flips or just flips. A flip is an operation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. We present two algorithms for planar tree transformations. The first technique is an indirect approach which relies on some ‘canonical’ tree to obtain such transformation results. It is shown that it takes at most 2n−m−s−2 flips (m,s>0) which is an improvement over the result in [D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65 (1996) 21-46]. Second, we present a direct approach which takes at most n−1+k flips (k?0) for such transformation when S in convex position and also show results when the points are in general position. We provide cases where the second technique performs an optimal number of flips. A counterexample is given to show that if |T₁?T₂|=k then they cannot be transformed to one another by k flips.     

Amortized efficiency of generating planar paths in convex position

Let S be a set of n?3 points arranged in convex position in the plane and suppose that all points of S are labeled from 1 to n in clockwise direction. A planar path P on S is a path whose edges connect all points of S with straight line segments such that no two edges of P cross. Flipping an edge on P means that a new path P^′ is obtained from P by a single edge replacement. In this paper, we provide efficient algorithms to generate all planar paths. With the help of a loopless algorithm to produce a set of 2-way binary-reflected Gray codes, the proposed algorithms generate the next planar path by means of a flip and such that the number of position changes for points in the path has a constant amortized upper bound.     

Negative selection algorithms on strings with efficient training and linear-time classification

A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σ^? into “normal” and “anomalous” partitions from a training set S containing only samples from the “normal” partition. The algorithm generates a set of patterns, called “detectors”, to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as “anomalous”. A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r-chunk and r-contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S⊆Σ^? and parameter r≤? one can construct an automaton whose acceptance behaviour is equivalent to the algorithm’s classification outcome. The resulting runtime is O(|S|?r|Σ|) for constructing the automaton in the training phase and O(?) for classifying a string.     

Computations on Nondeterministic Cellular Automata

This work concerns the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We assume that the space complexity is the diameter of area in space involved in computation. It is proved that (1) every nondeterministic cellular automata (NCA) of dimensionr, computing a predicatePwith time complexityT(n) and space complexityS(n) can be simulated byr-dimensional NCA with time and space complexityO(T^1/(r+1)S^r/(r+1)) and byr+1 dimensional NCA with time and space complexityO(T^1/2+S), whereTandSare functions constructible in time, (2) for any predicatePand integerr>1 if is a fastestr-dimensional NCA computingPwith time complexityT(n) and space complexityS(n), thenT=O(S), and (3) ifT_{r, P}is the time complexity of a fastestr-dimensional NCA computing predicatePthenT_r+1,P=O((T_{r, P})^1−r/(r+1)2),T_r+1,P=O((T_{r, P})^1+2/r).Similar problems for deterministic cellular automata (CA) are discussed.