Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 39 for “"Steiner tree problem"”.

  1. On the Integrality Gap of Directed Steiner Tree Problem

    In the Directed Steiner Tree problem, we are given a directed graph G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for every terminal t ∈ X. The only known polylogarithmic approximations for …

    waterloo Repository record for On the Integrality Gap of Directed Steiner Tree Problem (opens in a new tab)

  2. The Steiner Ratio for the Obstacle-Avoiding Steiner Tree Problem

    This thesis examines the (geometric) Steiner tree problem: Given a set of points P in the plane, find a shortest tree interconnecting all points in P, with the possibility of adding points outside P, called the Steiner points, as additional vertices of the tree. The Steiner tree problem has been …

    waterloo Repository record for The Steiner Ratio for the Obstacle-Avoiding Steiner Tree Problem (opens in a new tab)

  3. Topics in network optimization: The Steiner tree problem and semiconductor manufacturing

    … covers two very different topics related to problems defined on graphs. The first is a fundamental graph optimization problem called the Steiner tree problem. The second is an applied problem in semiconductor manufacturing. In the first part of this thesis, we propose a new approach to solve …

    gatech Repository record for Topics in network optimization: The Steiner tree problem and semiconductor manufacturing (opens in a new tab)

  4. Random methods for rectilinear steiner tree problem with applications in VLSI design

    … inter-connecting nodes on the chip. This problem can be represented as the shortest rectilinear Steiner spanning tree (SRSST) problem. To solve this problem two random methods. Simulated Annealing (SA) and Stochastic Evolution (SE) were investigated and implemented using an object oriented …

    ttu Repository record for Random methods for rectilinear steiner tree problem with applications in VLSI design (opens in a new tab)

  5. On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs

    The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in …

    waterloo Repository record for On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs (opens in a new tab)

  6. Node-Weighted Prize Collecting Steiner Tree and Applications

    The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph …

    waterloo Repository record for Node-Weighted Prize Collecting Steiner Tree and Applications (opens in a new tab)

  7. Iterative Rounding Approximation Algorithms in Network Design

    … approach to solving network design optimization problems ever since Jain introduced the concept in his revolutionary 2-approximation for the Survivable Network Design Problem (SNDP). This paper looks at several important iterative rounding approximation algorithms and makes improvements to some …

    waterloo Repository record for Iterative Rounding Approximation Algorithms in Network Design (opens in a new tab)

  8. Constrained Geometric Optimization Problems

    … we consider constrained geometric optimization problems. The first is a constrained version of the k-Steiner tree problem restricting the Steiner points to lie on a restricted set of curves. We solve the 1-Steiner tree problem in the Euclidean plane in optimal asymptotic time and space bounds …

    carleton Repository record for Constrained Geometric Optimization Problems (opens in a new tab)

  9. Online And Offline Facility Location And Network Design

    … and offline facility location and network design problems, including an offline facility location model with submodular opening costs, an online prize-collecting facility location model, an offline singledemand capacitated facility location model and an online prize-collecting Steiner tree …

    cornell Repository record for Online And Offline Facility Location And Network Design (opens in a new tab)

  10. Árvores de diâmetro mínimo sujeitas a restrição de orçamento

    … graph G = (V, E), we investigate three problems seeking minimum diameter trees of G. The definition used for the diameter of a tree, T = (VT , ET ), is the usual one. Namely, the number of edges in the path of T that contains the largest number of them. For any of the three problems, …

    brazil-uerj Repository record for Árvores de diâmetro mínimo sujeitas a restrição de orçamento (opens in a new tab)

  11. A Primal Dual Algorithm On 2-Steiner Graphs

    The Steiner Tree Problem is a fundamental network design problem, where the goal is to connect a subset of terminals of a given network at minimum cost. A major open question regarding this problem, is proving that the integrality gap of a certain linear program relaxation, called the bidirected …

    waterloo Repository record for A Primal Dual Algorithm On 2-Steiner Graphs (opens in a new tab)

  12. Partialk-trees: Algorithms and applications

    Partial k-trees are a recursively defined class of graphs that allow efficient algorithms for a variety of combinatorial optimization problems. An $O(n\sp2$) algorithm for the Bisection Width problem on partial k-trees is presented. The $O(n\sp2$) Bi-section width algorithm forms the basis for a …

    nebraska Repository record for Partialk-trees: Algorithms and applications (opens in a new tab)

  13. Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization

    … in combinatorial optimization. The following "Steiner tree problem" is central: given a graph with a distinguished subset of required vertices, and costs for each edge, find a minimum-cost subgraph that connects the required vertices. We also investigate the areas of network design, …

    waterloo Repository record for Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization (opens in a new tab)

  14. Algorithmic aspects of connectivity, allocation and design problems

    Most combinatorial optimization problems are NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to the optimal, have become a rich field …

    gatech Repository record for Algorithmic aspects of connectivity, allocation and design problems (opens in a new tab)

  15. Patent Collaboration and Team Formation

    The team formation problem has existed for many years in various guises. One important problem in the team formation problem is to produce small teams that have a required set of skills. We propose a framework that incorporates machine learning to predict unobserved links between collaborators, …

    maynooth Download PDF for Patent Collaboration and Team Formation (opens in a new tab)

  16. Two new algorithms for classical problems in computer science

    This thesis presents two algorithms dealing with problems in two classic algorithm areas in computer science. The first algorithm presents a simple solution to the selection problem. The sequential computing model form of this selection algorithm is presented first followed by a general parallel …

    unlv Repository record for Two new algorithms for classical problems in computer science (opens in a new tab) Download PDF for Two new algorithms for classical problems in computer science (opens in a new tab)

  17. MODELING AND OPTIMIZATION OF TRANSMISSION NETWORKS

    … In this dissertation, we consider two different problems associated with transmission networks: the dynamics on a data communication network and the optimal design of a general transmission network located on a non-uniform landscape. The first two parts of this dissertation develop and apply …

    maryland Repository record for MODELING AND OPTIMIZATION OF TRANSMISSION NETWORKS (opens in a new tab)

  18. Parameterized Approaches for Large-Scale Optimization Problems

    … we study challenging discrete optimization problems from the perspective of parameterized complexity. The usefulness of this type of analysis is twofold. First, it can lead to efficient algorithms for large-scale problem instances. Second, the analysis can provide a rigorous explanation for …

    tamu Repository record for Parameterized Approaches for Large-Scale Optimization Problems (opens in a new tab)

Page 1 of 2