Search

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H 1 , H 2) -free graphs and a dichotomy for the latter problem restricted to H -free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H -free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P ≠ NP). We also find that Edge Steiner Tree is polynomial-time solvable for (H 1 , H 2) -free graphs if and only if the treewidth of the class of (H 1 , H 2) -free graphs is bounded (subject to P ≠ NP). To obtain the latter result, we determine all pairs (H 1 , H 2) for which the class of (H 1 , H 2) -free graphs has bounded treewidth. [ABSTRACT FROM AUTHOR]

Abstract We introduce the concepts of k -lunes and k -lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems. [ABSTRACT FROM AUTHOR]

Abstract The Steiner distance of vertices in a set S is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets S of cardinality k is called the Steiner k -Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner k -Wiener index. The same extremal problems are also considered for trees with a given number of segments. [ABSTRACT FROM AUTHOR]

The prize-collecting Steiner tree problem in graphs (PCSPG) , as well as its rooted variant ( RPCST ), are target problems of the 11th DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenge held in collaboration with ICERM (the Institute for Computational and Experimental Research in Mathematics). To solve these two problems, this paper proposes a knowledge-guided local search algorithm (K-ILS), 1 1 This paper extends [15], which was presented at the workshop of the 11th DIMACS Implementation Challenge, but has not been formally published. which integrates dedicated search strategies and explores structure information of problem instances. K-ILS uses an effective swap-vertex operator for tree transformation associated with a discriminating auxiliary evaluation function as well as several knowledge-guided perturbation strategies. K-ILS additionally employs two new path-based move operators to generate neighboring solutions. The computational results achieved on the benchmark instances of the 11th DIMACS Implementation Challenge using the same computing platform and competition rules demonstrate that K-ILS performs very well compared to the leading algorithms of the challenge. We report additional experiments to analyze the impact of the key components to the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

• Show that an interesting transformation on trees is monotone with respect to the average Steiner 3-eccentricity. • Establish some sharp bounds on the average Steiner 3-eccentricity among trees with a given degree sequence (resp. segment sequence, number of segments). • Using the majorization theory and our obtained results to characterize extremal graphs among the trees with some given classical parameters. The Steiner k -eccentricity of a vertex in a graph G is the maximum Steiner distance over all k -subsets containing the vertex. The average Steiner k -eccentricity of G is the mean value of all vertices' Steiner k -eccentricities in G. Let T n be the set of all n -vertex trees, T n , Δ be the set of n -vertex trees with maximum degree Δ , T n , Δ k be the set of n -vertex trees with exactly k vertices of a given maximum degree Δ , and let MT n k be the set of n -vertex trees with exactly k vertices of maximum degree. In this paper, we first determine the sharp upper bound on the average Steiner 3-eccentricity of n -vertex trees with a given degree sequence. The corresponding extremal graphs are characterized. Consequently, together with majorization theory, all graphs among T n , Δ k (resp. T n , Δ , MT n k , T n) having the maximum average Steiner 3-eccentricity are identified. Then we characterize the unique n -vertex tree with a given segment sequence having the minimum average Steiner 3-eccentricity. Finally, we determine all n -vertex trees with a given number of segments having the minimum average Steiner 3-eccentricity. [ABSTRACT FROM AUTHOR]

We consider the problem of embedding the Steiner points of a Steiner tree with a given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. The task is to find an embedding minimizing the total length of the tree. We show that the problem can be formulated as simple linear programming. Moreover, we analyze the structure of feasible embeddings and give a combinatorial polynomial time algorithm for the problem. Our algorithm combines a dynamic programming approach and binary search and relies on the total unimodularity of a matrix appearing in a sub-problem. 1 [ABSTRACT FROM AUTHOR]

We show that the survivable bottleneck Steiner tree problem in normed planes can be solved in polynomial time when the number of Steiner points is constant. This is a fundamental problem in wireless ad-hoc network design where the objective is to design networks with efficient routing topologies. Our result holds for a general definition of survivability and for any norm whose ball is specified by a piecewise algebraic curve of bounded degree and with a bounded number of pieces. In particular, under the Euclidean and rectilinear norms our algorithm constructs an optimal solution in O ( n 2 k + 3 log ⁡ n ) steps, where n is the number of terminals and k is the number of Steiner points. Our algorithm is based on the construction of generalised Voronoi diagrams and relative neighbourhood graphs. [ABSTRACT FROM AUTHOR]

Abstract: We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in time, where tw is the graphʼs treewidth and the Bell number is the number of partitions of a k-element set. This is a linear-time algorithm for graphs with fixed treewidth and a polynomial algorithm for . While being faster than the previously known algorithms, the coloring scheme used in our algorithm can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems with similar runtime bounds. [Copyright &y& Elsevier]

Abstract: Hybrid approaches are often recommended for dealing in an efficient manner with complex problems that require considerable computational time. In this study, we follow a similar approach consisting of combining spectral clustering and ant colony optimization in a two-stage algorithm for the purpose of efficiently solving the Steiner tree problem in large graphs. The idea of the two-stage approach, called ESC–IAC, is to apply a divide-and-conquer strategy which consists of breaking down the problem into sub-problems to find local solutions before combining them. In the first stage, graph segments (clusters) are generated using an ensemble spectral clustering method for enhancing the quality; whereas in the second step, parallel independent ant colonies are implemented to find local and global minima of the Steiner tree. To illustrate the efficiency and accuracy, ESC–IAC is applied in the context of a geographical application relying on real-world as well as artificial benchmarks. [Copyright &y& Elsevier]

Abstract: Given an instance of an optimization problem together with an optimal solution for it, a reoptimization problem asks for a solution for a locally modified input instance. In this paper we develop new reoptimization techniques and apply them to the Steiner Tree Problem. Our techniques significantly improve the previous results and apply to a variety of reoptimization problems. [Copyright &y& Elsevier]

Abstract: This paper investigates the quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the Prize Collecting Steiner Tree Problem (PCSTP) on a graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, node prizes and penalties, as well as a preset quota, the PCSTP seeks to find a subtree that includes the root node and collects a total prize not smaller than the specified quota, while minimizing the sum of the total edge costs of the tree plus the penalties associated with the nodes that are not included in the subtree. For this challenging network design problem that arises in telecommunication settings, we present two valid 0-1 programming formulations and use them to develop preprocessing procedures for reducing the graph size. Also, we design an optimization-based heuristic that requires solving a PCSTP on a specific tree-subgraph. Although, this latter special case is shown to be -hard, it is effectively solvable in pseudo-polynomial time. The worst-case performance of the proposed heuristic is also investigated. In addition, we describe new valid inequalities for the PCSTP and embed all the aforementioned constructs in an exact row-generation approach. Our computational study reveals that the proposed approach can solve relatively large-scale PCSTP instances having up to 1000 nodes to optimality. [Copyright &y& Elsevier]

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph with a cost function and two subsets and satisfying , a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in such that each vertex in cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a-approximation algorithm for the problem, where is the best-known approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: 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]. [Copyright &y& Elsevier]

The Steiner ratio is the greatest lower bound of the ratios of the Steiner Minimal Tree- by the Minimum Spanning Tree-lengths running over all finite subsets of a metric space. We will discuss this quantity for finite-dimensional Banach spaces of high dimension. Particularly, let the quantity Cd defined as the upper bound of the Steiner ratio of all d-dimensional Banach spaces, thenlimlower limit d→∞ Cd=limlower limit d→∞ md(B(2)),where md(B(2)) denotes the Steiner ratio of the d-dimensional Euclidean space. [Copyright &y& Elsevier]

Abstract: Suppose that is a simple graph. Let and be the geodetic number and the Steiner number of , respectively. In this note, we prove that, for any nonnegative integers , and with and , there exists a connected graph with , , and where and are the radius and diameter of , respectively. This result answers the conjecture of Chartrand and Zhang [G. Chartrand, P. Zhang, The Steiner number of a graph, Discrete Math. 242 (2002) 41–54]. [Copyright &y& Elsevier]