Search

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

For a connected graph G of order p and a set S ⊆ V (G) , the Steiner distance of S is the minimum number of edges in a connected subgraph of G containing S. If n is an integer, 2 ≤ n ≤ p and a vertex v ∈ V (G) , the Steiner n -eccentricity of a vertex v of G , ex n (v) , is the maximum Steiner distance of all n -subsets of V (G) containing v. The Steiner n -radius of G , rad n (G) , is the minimum Steiner n -eccentricities of all vertices in G. We give bounds on rad n (G) in terms of the order of G and the minimum degree of G for all graphs and for graphs that contain no triangles. We shall also investigate the relation between the n -radius of a graph G and its complement Ḡ. [ABSTRACT FROM AUTHOR]

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\'a, SIAM J. Comput., 10 (1981), pp. 270--283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290--306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815--825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632--645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) 967 1120 + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP'14, Springer, Berlin, 2014, pp. 800--811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we "open the box" and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area. [ABSTRACT FROM AUTHOR]

The Steiner k -eccentricity of a vertex v of a graph G is the maximum Steiner distance over all k -subsets of V (G) which contain v. In this paper Steiner 3-eccentricity is studied on trees. Some general properties of the Steiner 3-eccentricity of trees are given. A tree transformation which does not increase the average Steiner 3-eccentricity is given. As its application, several lower and upper bounds for the average Steiner 3-eccentricity of trees are derived. [ABSTRACT FROM AUTHOR]

The Euclidean k -Steiner tree problem asks for a minimum-cost network connecting n given points in the plane, allowing at most k additional nodes referred to as Steiner points. In the classical Steiner tree problem in which there is no restriction on the number of nodes, every Steiner point must be of degree 3. The k -Steiner problem differs in that Steiner points of degree 4 may be included in an optimal solution. This simple change leads to a number of complexities when attempting to create a generation algorithm for optimal k -Steiner trees, which has proven to be a powerful component of the flagship algorithm, namely GeoSteiner, for solving the classical Steiner tree problem. In the present paper we firstly extend the basic framework of GeoSteiner's generation algorithm to include degree-4 Steiner points. We then introduce a number of novel results restricting the structural and geometric properties of optimal k -Steiner trees, and then show how these properties may be used as topological pruning methods underpinning our generation algorithm. Finally, we present experimental data to show the effectiveness of our pruning methods in reducing the number of sub-optimal solution topologies. [ABSTRACT FROM AUTHOR]

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]

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be sansA sansP sansX -hard, and sansW [sanstwo ]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (sansE sansP sansA sansS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (sansP sansS sansA sansK sansS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an sansE sansP sansA sansS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is sansA sansP sansX -hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is sansW [sansone ]-hard. Nevertheless, we show that an sansE sansP sansA sansS exists for Unweighted Directed Steiner Tree, but a sansP sansS sansA sansK sansS does not. We also prove that there is an sansE sansP sansA sansS and a sansP sansS sansA sansK sansS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter. [ABSTRACT FROM AUTHOR]

In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of k-restricted full components for some k ≥ 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for k → ∞. However, the running time is also exponentially dependent on k, so only small k are tractable in practice. We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact algorithm based on integer linear programs, and to fast and simple 2-approximations as well as state-of-the-art heuristics. [ABSTRACT FROM AUTHOR]

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F ⊆ E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and |E(T)|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and that has size polynomial in |C|. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w(f), and an accuracy parameter ε > 0, uncovers a set F ⊆ E(G) of total weight at most poly(ε-1) w(f) that, for any set of terminal pairs that lie on f, contains a Steiner forest within additive error ε w(f) from the optimal Steiner forest. [ABSTRACT FROM AUTHOR]

This article presents an approximation algorithm for the Steiner connectivity problem, which is a generalization of the Steiner tree problem that involves paths instead of edges. The problem can also be seen as hypergraph‐version of the Steiner tree problem; it arises in line planning in public transport. We prove a k + 1 approximation guarantee, where k is the minimum of the maximum number of nodes in a path minus 1 and the maximum number of terminal nodes in a path. The result is based on a structural degree property for terminal nodes. [ABSTRACT FROM AUTHOR]

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and , the Steiner distance dG(S) among the vertices of S is the minimum size among all connected subgraphs whose vertex sets contain S. Let n, k be two integers with 2 ≤ k ≤ n. Then the Steiner k-eccentricity ek(v) of a vertex v of G is defined by . Furthermore, the Steiner k-diameter of G is . In 2011, Chartrand, Okamoto and Zhang showed that k − 1 ≤ sdiamk(G) ≤ n − 1. In this paper, graphs with sdiam4( G) = 3, 4, n − 1 are characterized, respectively. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) are communication networks having tiny sensors with sensing and transmitting capabilities. These systems adopting traditional routing protocols to organize communication, have design issues, and quality of service is still a challenging research factor. The key idea of this research is to discover the most efficient routing protocols based on the design of a reliable and efficient routing protocol to determine quality of services in a WSN. In this paper we propose a reliable and efficient path selection strategy by designing a Quality of Service Aware multicast routing protocol. This protocol discusses the multicast routing problem of WSN with multiple QoS constraints, by discovering a minimum resource consumption path while satisfying multiple constraints optimization conditions. Simulation results show that the fair link selection strategy can yield to a good solution for this traditionally NP complex problem, as compared to the best multicast algorithms known. [ABSTRACT FROM AUTHOR]

The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime O(r(r + s - 1) · wmax ), where r, s, and wmax are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph.We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance. [ABSTRACT FROM AUTHOR]

Dirac showed that in a ( k − 1 ) -connected graph there is a path through each k vertices. The path k -connectivity π k ( G ) of a graph G , which is a generalization of Dirac’s notion, was introduced by Hager in 1986. It is natural to introduce the concept of path k -edge-connectivity ω k ( G ) of a graph G . Denote by G ○ H the lexicographic product of two graphs G and H . In this paper, we prove that ω 3 ( G ∘ H ) ≥ ω 3 ( G ) ⌊ 3 | V ( H ) | 4 ⌋ for any two graphs G and H . Moreover, the bound is sharp. We also derive an upper bound of ω 3 ( G ○ H ), that is, ω 3 ( G ∘ H ) ≤ min { 2 ω 3 ( G ) | V ( H ) | 2 , δ ( H ) + δ ( G ) | V ( H ) | } . We demonstrate the usefulness of the proposed constructions by applying them to some instances of lexicographic product networks. [ABSTRACT FROM AUTHOR]

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by $$|T|+k$$ , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals | T| is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs. [ABSTRACT FROM AUTHOR]

Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(\sqrt n\log n) , the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data. [ABSTRACT FROM PUBLISHER]

In this article, we consider the Node-Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node-induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node-cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition-based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well-known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 33-51 2017 [ABSTRACT FROM AUTHOR]

In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we focus on binary Steiner trees in which all node degrees are required to be at most three. It is shown that finding a binary Steiner tree is NP -complete for arbitrary graphs. We relate the problem to Steiner trees without degree constraints as well as degree-constrained spanning trees by proving approximation ratios. Further, we give integer programming formulations for this problem on undirected and directed graphs and study the associated polytopes for both cases. Some classes of facets are introduced. Based on this study a branch-&-cut approach is developed and evaluated on biological instances coming from the reconstruction of phylogenetic trees. We are able to solve nearly all instances up to 200 nodes to optimality within a limited amount of time. This shows the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

A complete weighted graph, $$G(X,\varGamma ,W)$$ , is considered. Let $$\tilde{X}\subset X$$ be some subset of vertices and, by definition, a Steiner tree is any tree in the graph G such that the set of the tree vertices includes set $$\tilde{X}$$ . The Steiner tree problem consists of constructing the minimum-length Steiner tree in graph G, for a given subset of vertices $$\tilde{X}$$ The effectively computable estimate of the minimal Steiner tree is obtained in terms of the mean value and the variance over the set of all Steiner trees. It is shown that in the space of the lengths of the graph edges, there exist some regions where the obtained estimate is better than the minimal spanning tree-based one. [ABSTRACT FROM AUTHOR]

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario-based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch-and-cut solution method. We also propose an LP-based separation for the scenario-based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch-and-cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch-and-cut method demonstrates the strength of the scenario-based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321-334, 2015 [ABSTRACT FROM AUTHOR]

A convergent product is an assembly shape concept integrating functions and sub-functions to form a final product. To conceptualize the convergent product problem, a web-based network is considered in which a collection of base functions and sub-functions configure the nodes, and each arc in the network is considered to be a link between two nodes. The aim is to find an optimal tree of functionalities in the network, adding value to the product in the web environment. First, an algorithm is proposed to assign the links among bases and sub-functions. Then, numerical values, as benefits and costs, are determined for arcs and nodes, respectively, using a mathematical approach. Also, customer value corresponding to the benefits is considered. Finally, the Steiner tree methodology is adapted to a multi-objective model optimized by an augmented ε-constraint method. An example is worked out to illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

For a set $$W$$ of vertices of a connected graph $$G=(V(G),E(G))$$ , a Steiner W-tree is a connected subgraph $$T$$ of $$G$$ such that $$W\subseteq V(T)$$ and $$|E(T)|$$ is minimum. Vertices in $$W$$ are called terminals. In this work, we design an algorithm for the enumeration of all Steiner $$W$$ -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner $$W$$ -tree in polynomial time, our algorithm enumerates the remaining trees with $$O(n)$$ delay (where $$n=|V(G)|$$ ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966-984, ), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given $$W$$ and a vertex $$x\in V(G)\setminus W$$ , is $$x$$ in a Steiner $$W'$$ -tree for some $$\emptyset \ne W' \subseteq W$$ ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when $$W$$ has arbitrary size. In addition, we prove that deciding whether $$x$$ is in some Steiner $$W$$ -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs. [ABSTRACT FROM AUTHOR]

The roll-out of new infrastructural networks in space-constrained areas requires the careful consideration of limited paths. This design task is aggravated if the number and/or location of connectors is unknown. The novel combination of graph theory and concepts of exploratory modelling in this contribution allow for an analysis of most likely paths that maximise the value for the planners. We apply this approach to two proposed energy networks in the Netherlands: a biogas network of farmers in the province of Overijssel and an LNG pipeline connecting industries in the Port of Rotterdam. The examples demonstrate the ease of use and simplicity of this approach that transparently deals with unknowns. [ABSTRACT FROM AUTHOR]

Abstract: Simultaneous equations models can be solved with a variety of algorithms. Some methods use the QR-decomposition of several matrices associated to the equations in the system. To accelerate the computation of those QR-decompositions and consequently the solution of simultaneous equations models, the QR-decomposition of a matrix associated to an equation can be obtained from that of another matrix associated to another equation which contains the variables of the first equation. A Steiner tree can be used, with nodes representing the equations in the model and with edges whose associated weight is the cost of computing the QR-decomposition of an equation from that of another equation. The Steiner tree of the graph associated to the simultaneous equations model gives the order of computation of the QR-decompositions of lowest computational cost. But the number of nodes in the graph is very large, and exact methods to obtain the Steiner tree are not applicable. In this paper, the application of heuristics and metaheuristics to approach the Steiner tree of the graph associated to a simultaneous equations model is considered. A heuristic and a genetic algorithm are presented and analyzed. The quality of the tree obtained and its usability in an algorithm to solve simultaneous equations models efficiently is experimentally studied. [Copyright &y& Elsevier]

An important manufacturing technology spectrum is to consider rapid and sensitive assemblies through convergent product (CP) in digital environment. We integrate functions and sub-functions using a comprehensive mathematical optimization process. To form the CP, a web-based fuzzy network is considered in which a collection of base functions and sub-functions configure the nodes and each arc in the network is to be a link between two nodes. The aim is to find an optimal tree of functionalities in the network adding value to the product in the web environment. First, a purification process is performed in the product network to assign the links among bases and sub-functions. Then, fuzzy numbers as benefits, costs and customers' value are determined. Next, the fuzzy Steiner tree methodology is adapted to a multi-objective model of the network to find the optimal tree determining the value adding sub-functions to bases in a CP. A new fuzzy multi-objective optimization is developed to work out the problem. Finally, an example is worked out to illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

Due to the harsh battlefield surroundings and violent nature of intelligent minefield network applications, the minefield network sometimes suffers a large-scale damage that involves several nodes and would thus create multiple disjoint partitions. A novel strategy for repairing such damage was investigated by modeling this problem as Steiner minimum tree problem. At first, a grid model of minefield area that limits the search space to a more manageable size was proposed. And then, according to combinated optimization algorithm of quantum discrete particle swarm optimization (QDPSO) and jumping frogs optimization (JFO), the position of relay nodes was confirmed and the minefield network was repaired. The simulation results demonstrate the effectiveness of the proposed recovery algorithm which has less computation- al time. Compared with the other algorithms, the proposed algorithm obtains more promising results in the average path length and the network life cycle. [ABSTRACT FROM AUTHOR]

Abstract: Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G. We improve Lauʼs result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimiʼs criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem. [Copyright &y& Elsevier]

We present a heuristic for the Euclidean Steiner tree problem in ℜ for d≥2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in ℜ for 2≤ d≤5. [ABSTRACT FROM AUTHOR]

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: We present a polynomial-time approximation scheme (PTAS) for the Steiner tree problem with polygonal obstacles in the plane with running time , where n denotes the number of terminals plus obstacle vertices. To this end, we show how a planar spanner of size can be constructed that contains a -approximation of the optimal tree. Then one can find an approximately optimal Steiner tree in the spanner using the algorithm of Borradaile et al. (2007) for the Steiner tree problem in planar graphs. We prove this result for the Euclidean metric and also for all uniform orientation metrics, i.e. particularly the rectilinear and octilinear metrics. [Copyright &y& Elsevier]

A minimum connected dominating set (MCDS) is used as virtual backbone for efficient routing and broadcasting in ad hoc sensor networks. The minimum CDS problemis NP-complete even in unit disk graphs. Many heuristics-based distributed approximation algorithms for MCDS problems are reported and the best known performance ratio has (4:8 + ln 5). We propose a new heuristic called collaborative cover using two principles: 1) domatic number of a connected graph is at least two and 2) optimal substructure defined as subset of independent dominator preferably with a common connector. We obtain a partial Steiner tree during the construction of the independent set (dominators). A final postprocessing step identifies the Steiner nodes in the formation of Steiner tree for the independent set of G. We show that our collaborative cover heuristics are better than degree-based heuristics in identifying independent set and Steiner tree. While our distributed approximation CDS algorithm achieves the performance ratio of (4:8 + ln 5)opt + 1:2, where opt is the size of any optimal CDS, we also show that the collaborative cover heuristic is able to give a marginally better bound when the distribution of sensor nodes is uniform permitting identification of the optimal substructures. We show that the message complexity of our algorithm is O(nΔ2);Δ being the maximum degree of a node in graph and the time complexity is O(n). [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]

Abstract: Let be a gradient-constrained minimum network, that is, a minimum length network spanning a given point set in 3-dimensional space with edges that are constrained to have gradients no more than an upper bound . Such networks occur in underground mines where the slope of the declines (tunnels) cannot be too steep due to haulage constraints. Typically the gradient is less than 1/7. By defining a new metric, the gradient metric, the problem of finding can be approached as an unconstrained problem where embedded edges can be considered as straight but measured according to their gradients. All edges in are labelled by their gradients, being or , in the gradient metric space. Computing Steiner points plays a central role in constructing locally minimum networks, where the topology is fixed. A degree-3 Steiner point is labelled minimal if the total length of the three adjacent edges is minimized for a given labelling. In this paper we derive the formulae for computing labelled minimal Steiner points. Then we develop an algorithm for computing locally minimal Steiner points based on information from the labellings of adjacent edges. We have tested this algorithm on uniformly distributed sets of points; our results help in finding gradient-constrained minimum networks. [Copyright &y& Elsevier]

Abstract: Given an instance of the Steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. In this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. Our results are as follows: (i) We prove that these reoptimization variants of the Steiner tree problem are NP-hard, even if edge costs are restricted to values from . (ii) We design 1.5-approximation algorithms for both variants of local modifications. This is an improvement over the currently best known approximation algorithm for the classical Steiner tree problem which achieves an approximation ratio of . (iii) We present a PTAS for the subproblem in which the edge costs are natural numbers for some constant . [Copyright &y& Elsevier]

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n). [ABSTRACT FROM AUTHOR]

Abstract: We define basic networks as the undirected subgraphs with minimal number of units in which the distances (geodesics, minimal path lengths) among a set of selected nodes, which we call seeds, in the original graph are conserved. The additional nodes required to draw the basic network are called connectors. We describe a heuristic strategy to find the basic networks of complex graphs. We also show how the characterization of these networks may help to obtain relevant biological information from highly complex protein–protein interaction data. [Copyright &y& Elsevier]

Given a set of pins and a set of obstacles on routing layers, a multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many very large scale integration designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. As a fundamental problem with extensive practical applications to routing and wirelength/congestion/timing estimations in early design stages, it is desired to develop an effective algorithm for the ML-OARSMT problem to facilitate the design flow. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem with rectangular obstacles and then identify key different properties of this problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph, we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any two-pin net and many multiple-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature. [ABSTRACT FROM AUTHOR]

The study of spanning trees and Steiner trees arises naturally in applications, such as in the design of integrated circuit boards, communication networks, power networks and pipelines of minimum cost. In such applications the Steiner ratio is an indication of how badly a minimum spanning tree performs compared to a Steiner minimal tree. In this paper a short proof is presented for the Steiner ratio for points on a triangular lattice in the Euclidean plane. A Steiner tree in two dimensions is \lifted" to become a rectilinear tree in three dimensions, where it is altered. The rectilinear tree is then projected back into the plane and the result readily follows. A short note at the end of the paper compares our three- dimensional rectilinear trees to \impossible objects" such as Escher's "Waterfall." [ABSTRACT FROM AUTHOR]

The Steiner tree problem is an intractable optimization problem, which asks for a network, in fact a tree, interconnecting a given point set V in a metric space and minimizing the total length of the network. The tree topology t of the network is called a Steiner topology and a tree T with minimum length with respect to its Steiner topology is called a Steiner tree. As a combinatorial optimization problem, the Steiner tree problem asks for a Steiner tree T with minimum length over all possible topologies t on V. It has been proved that if T is in E^3 then the length of T cannot be expressed by radicals even when T spans just 4 points. For such optimization problems in which the objective functions do not have closed form solutions the traditional approach is approximation. In this paper we propose a new approach by introducing some new concepts: equivalence, indicators and quasi-indicators, and then we apply these concepts to the Steiner tree problem. Roughly speaking, a quasi-indicator is a function that is simple to compute but indicates with high probability the optimal solution to the original optimisation problem. For a specific optimisation problem – finding the optimal Steiner topologies on 4 points in space, we demonstrate how to find good quasiindicators. The extensive computational experiments over 5000 random 4-point sets show that the best quasi-indicator for finding optimal Steiner topologies on 4 points in space is not only easy to compute but also extremely successful with less than 1.5% failures in indicating optimal topologies even if degeneracy of Steiner minimal trees exists. Moreover, within the 1.5% cases of failure, the maximum and the average relative error are 1.5% and 0.2% respectively. Therefore, the performance of the proposed Q-indicator is very good and could be applied to the four vertices surrounding any pair of adjacent Steiner points in a Steiner tree on n (> 4) points in space to make local improvements to the topology of the Steiner minimal tree in space. [ABSTRACT FROM AUTHOR]

Abstract: We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in . Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology we use a conic formulation for the problem of locating the Steiner points to obtain a rigorous lower bound on the minimal tree length. We also show how to obtain lower bounds on the child problems at a given node without actually computing the minimal Steiner trees associated with the child topologies. These lower bounds reduce the number of children created and also permit the implementation of a “strong branching” strategy that varies the order in which the terminal nodes are added. Computational results demonstrate substantial gains compared to Smith’s original algorithm. [Copyright &y& Elsevier]

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing routes for source coding with explicit side information (i.e., with side information at both the encoder and the decoder) in sensor networks. Two difficulties in constructing such data-centric routes are the lack of reasonably practical data aggregation models and the high computational complexity resulting from the coupling of routing and in-network data fusion. Our data aggregation model is built upon the observation that in many physical situations the side information providing the most coding gain comes from a small number of nearby sensors. Based on this model, we formulate an optimization problem to minimize the communication cost, and show that finding the exact solution of this problem is NP-hard. Subsequently, two suboptimal algorithms are proposed. One is inspired by the balanced trees that have small total weights and reasonable distance from each sensor to the fusion center [6]. The other separately routes the explicit side information to achieve cost minimization. Bounds on the worst-case performance ratios of two methods to the optimal solution are derived for a special class of rate models, and simulations are conducted to shed light on their average behaviors. [ABSTRACT FROM AUTHOR]

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y-/X-architecture (λ3-/λ4-geometry) to improve the chip performance. This paper presents an O(n log n) heuristic, λ-OAT, for obstacle-avoiding Steiner minimal tree construction in the A-geometry plane (λ-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with most recent works on OARSMT problem, A-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of λ-OAT make it extremely practical and useful in the routing phase. [ABSTRACT FROM AUTHOR]

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]

Many network services must ensure stable QoS (Quality of Service) and provide acceptable link costs, time delay, bandwidth and pack loss constraints, essentially a multicast routing problem. Computing such multicast routing problems is an NP-complete problem. In this paper, we propose a genetic algorithm using fuzzy selection and local search (GFLS), to address the multicast routing problem with QoS under delay constraints. The GFLS algorithm finds a multicast tree with minimum cost under delay constraints. The primary simulation results demonstrate that the GFLS can efficiently solve a multicast routing problem under QoS constraints. [ABSTRACT FROM AUTHOR]

We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are purchased in a first stage when only probabilistic information about the second stage is available. In the second stage, one of a finite number of specified scenarios is realized, which results in the set of terminals becoming known and the opportunity to purchase additional edges (under an inflated cost function) to augment the first-stage solution. We provide constant factor approximation algorithms for these problems by rounding the linear relaxation of IP formulations of the problems. Our algorithms involve solving the linear relaxation first, followed by a primal-dual routine that is guided by the LP solution. We also show that because our bounds are local (the cost of each component is bounded by its cost in the LP solution), we are able to obtain bounds that guard against a form of downside risk. [ABSTRACT FROM AUTHOR]