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 68 for “"steiner tree"”.

  1. 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)

  2. 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)

  3. 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)

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

    … 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 the Steiner tree problem when the number of terminal nodes is fixed. The Steiner tree problem …

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

  5. Garnet: A graph-based octilinear mixed-signal Steiner tree routing system

    … IC router can efficiently construct near-minimal Steiner trees for multi-terminal nets in both classical rectilinear, or Manhattan, geometry as well as octilinear geometries. These Steiner trees can be constructed around blockages, and in the presence of obstacles such as other nets. A method for …

    arizona-thes Repository record for Garnet: A graph-based octilinear mixed-signal Steiner tree routing system (opens in a new tab)

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

    … 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 design. Both Simulated Annealing and Stochastic …

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

  7. AN APPROACH FOR GLOBAL ROUTING IN VLSI LAYOUT BASED ON A NEW RECTILINEAR STEINER TREE ALGORITHM

    … and more crucial to IC design. The rectilinear Steiner Tree problem has received considerable attention in the last few years because of its wide variety of practical applications. Due to its rectilinear constraints, the problem also manifests itself in a variety of different aspects of VLSI …

    nus Repository record for AN APPROACH FOR GLOBAL ROUTING IN VLSI LAYOUT BASED ON A NEW RECTILINEAR STEINER TREE ALGORITHM (opens in a new tab) Download file for AN APPROACH FOR GLOBAL ROUTING IN VLSI LAYOUT BASED ON A NEW RECTILINEAR STEINER TREE ALGORITHM (opens in a new tab)

  8. 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)

  9. Graph Sparsification with Priority

    … include but are not limited to spanning trees (preserving connectivity), Steiner trees and forests (preserving connectivity between certain vertices or vertex pairs), spanners and emulators (preserving distances up to given error), distance preservers, cut and spectral sparsifiers, and …

    arizona-thes Repository record for Graph Sparsification with Priority (opens in a new tab)

  10. Iterative Rounding Approximation Algorithms in Network Design

    … basic feasible solutions of the Prize-Collecting Steiner Tree problem, and introduce a new problem that arises, which we call the Prize-Collecting Generalized Steiner Tree problem.

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

  11. 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)

  12. New Algorithmic Solutions for Some Clustering and Network Design Problems

    … with degree constraints, including Group Steiner Tree (on Trees), Directed Steiner Tree, and Single-Commodity Buy-at-Bulk.

    buffalo Repository record for New Algorithmic Solutions for Some Clustering and Network Design Problems (opens in a new tab)

  13. Exploiting level sensitive latches in wire pipelining

    … latches in wire pipelining. The user gives a Steiner tree, having a signal source and set of destination or sinks, and the location in rectangular plane, capacitive load and required arrival time at each of the destinations. The user also defines a library of non-clocked (buffer) elements and …

    tamu Repository record for Exploiting level sensitive latches in wire pipelining (opens in a new tab)

  14. 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 when the Steiner point is constrained to lie on an input …

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

  15. Online And Offline Facility Location And Network Design

    … location model and an online prize-collecting Steiner tree problem. In this thesis, we present algorithms for these problems and their approximation ratio or competitive ratio analysis.

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

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

    … 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, costs are associated with the edges …

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

  17. 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)

  18. Interconnect optimizations for nanometer VLSI design

    … buffering-aware over-the- block rectilinear Steiner minimum tree (BOB-RSMT) algorithm which helps reclaim the “wasted” over-the-block routing resources while meeting user-specified slew constraints. Proposed algorithm incrementally and efficiently migrates initial tree structures with …

    texas Repository record for Interconnect optimizations for nanometer VLSI design (opens in a new tab)

Page 1 of 4