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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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 …
-
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.
-
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 …
-
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 …
-
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.
-
Á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 …
-
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 …
-
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 …
Page 1 of 4