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.     

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.     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

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.     

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.     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

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.     

On the partial terminal Steiner tree problem

We investigate a practical variant of the well-known graph Steiner tree problem. For a complete graph G = ( V,E ) with length function l:E → R ⁺ and two vertex subsets R ⊂ V and R ′ ⊆ R, a partial terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R ∖ R ′ belong to the leaves of this Steiner tree. The partial terminal Steiner tree problem is to find a partial terminal Steiner tree T whose total lengths ∑ _{(u,v) ∈T} l ( u,v ) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem.

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.     

On efficient implementation of an approximation algorithm for the Steiner tree problem

Summary This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1–1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E _g¦+¦V _g–S¦log¦V _g–S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log (M,¦V _g–S¦)) time for sparse graph G, where E _g is the set of edges in G, V_g is the set of vertices in G, M = min {¦E _g, (¦V _g–S¦–1)²/2} and (x,y) = min {i¦log⁽ⁱ⁾ y x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V _g¦ vertices and ¦E _g¦ edges and the minimum spanning tree of a graph with ¦V _g–S¦ vertices and M edges.     

A fast algorithm for Steiner trees

Summary Given an undirected distance graph G=(V, E, d) and a set S, where V is the set of vertices in G, E is the set of edges in G, d is a distance function which maps E into the set of nonnegative numbers and SV is a subset of the vertices of V, the Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. In this paper, we analyze a heuristic algorithm for the Steiner tree problem. The heuristic algorithm has a worst case time complexity of O(¦S¦¦V¦ ²) on a random access computer and it guarantees to output a tree that spans S with total distance on its edges no more than 2(1–1/l) times that of the optimal tree, where l is the number of leaves in the optimal tree.     

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.     

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree-constrained node-weighted Steiner tree problem: We are given an undirected graph G(V,E) , with a nonnegative integral function d that specifies an upper bound d(v) on the degree of each vertex v ∈ V in the Steiner tree to be constructed, nonnegative costs on the nodes, and a subset of k nodes called terminals. The goal is to construct a Steiner tree T containing all the terminals such that the degree of any node v in T is at most the specified upper bound d(v) and the total cost of the nodes in T is minimum. Our main result is a bicriteria approximation algorithm whose output is approximate in terms of both the degree and cost criteria—the degree of any node v ∈ V in the output Steiner tree is O(d(v) log k) and the cost of the tree is O(log k) times that of a minimum-cost Steiner tree that obeys the degree bound d(v) for each node v . Our result extends to the more general problem of constructing one-connected networks such as generalized Steiner forests. We also consider the special case in which the edge costs obey the triangle inequality and present simple approximation algorithms with better performance guarantees. Received December 21, 1998; revised September 24, 1999.     

Steiner systems <Emphasis Type="Italic">S</Emphasis>(<Emphasis Type="Italic">v,k, k</Emphasis> − 1): Components and rank

For an arbitrary Steiner system S(v, k, t), we introduce the concept of a component as a subset of a system which can be transformed (changed by another subset) without losing the property for the resulting system to be a Steiner system S(v, k, t). Thus, a component allows one to build new Steiner systems with the same parameters as an initial system. For an arbitrary Steiner system S(v, k, k − 1), we provide two recursive construction methods for infinite families of components (for both a fixed and growing k). Examples of such components are considered for Steiner triple systems S(v, 3, 2) and Steiner quadruple systems S(v, 4, 3). For such systems and for a special type of so-called normal components, we find a necessary and sufficient condition for the 2-rank of a system (i.e., its rank over \mathbbF₂\mathbb{F}_2) to grow under switching of a component. It is proved that for k ≥ 5 arbitrary Steiner systems S(v, k, k − 1) and S(v, k, k − 2) have maximum possible 2-ranks.     

An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of thebottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to beNP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √2 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio—√2+∈ is proposed, for any ∈>0. Supported partially by Shandong Province Excellent Middle-Aged and Young Scientists Encouragement Fund (Grant No.03BS004) and the Ministry of Education Study Abroad Returnees Research Start-up Fund, and the National Natural Science Foundation of China (Grant No.60273032).     

Image Deblurring in the Presence of Impulsive Noise

Consider the problem of image deblurring in the presence of impulsive noise. Standard image deconvolution methods rely on the Gaussian noise model and do not perform well with impulsive noise. The main challenge is to deblur the image, recover its discontinuities and at the same time remove the impulse noise. Median-based approaches are inadequate, because at high noise levels they induce nonlinear distortion that hampers the deblurring process. Distinguishing outliers from edge elements is difficult in current gradient-based edge-preserving restoration methods. The suggested approach integrates and extends the robust statistics, line process (half quadratic) and anisotropic diffusion points of view. We present a unified variational approach to image deblurring and impulse noise removal. The objective functional consists of a fidelity term and a regularizer. Data fidelity is quantified using the robust modified L ¹ norm, and elements from the Mumford-Shah functional are used for regularization. We show that the Mumford-Shah regularizer can be viewed as an extended line process. It reflects spatial organization properties of the image edges, that do not appear in the common line process or anisotropic diffusion. This allows to distinguish outliers from edges and leads to superior experimental results.     

Wireless network design via 3-decompositions

We consider some network design problems with applications for wireless networks. The input for these problems is a metric space (X,d) and a finite subset UX of terminals. In the Steiner Tree with Minimum Number of Steiner Points (STMSP) problem, the goal is to find a minimum size set SX−U of points so that the unit-disc graph of S+U is connected. Let Δ be the smallest integer so that for any finite VX for which the unit-disc graph is connected, this graph contains a spanning tree with maximum degree Δ. The best known approximation ratio for STMSP was Δ−1 [I.I. Măndoiu, A.Z. Zelikovsky, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Information Processing Letters 75 (4) (2000) 165–167]. We improve this ratio to (Δ+1)/2+1+ε.In the Minimum Power Spanning Tree (MPST) problem, V=X is finite, and the goal is to find a “range assignment” on the nodes so that the edge set contains a spanning tree, and ∑_vVp(v) is minimized. We consider a particular case {0,1}-MPST of MPST when the distances are in {0,1}; here the goal is to find a minimum size set SV of “active” nodes so that the graph (V,E₀+E₁(S)) is connected, where , and E₁(S) is the set the edges in with both endpoints in S. We will show that the (5/3+ε)-approximation scheme for MPST of [E. Althaus, G. Calinescu, I. Măndoiu, S. Prasad, N. Tchervenski, A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks 12 (3) (2006) 287–299] achieves a ratio 3/2 for {0,1}-distances. This answers an open question posed in [E. Lloyd, R. Liu, S. Ravi, Approximating the minimum number of maximum power users in ad hoc networks, Mobile Networks and Applications 11 (2006) 129–142].