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 16 of 16 for “"Steiner tree"”.
-
The Prize Collecting Steiner Tree problem
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.
-
Optimization problems in network connectivity
… for constructing cut sparsifiers. -- Online Steiner Tree. Given an undirected graph as input, the goal of the Steiner tree problem is to select its minimum cost subgraph that connects a designated subset of vertices. We give the first online algorithm for the Steiner tree problem that has a …
-
Patent Collaboration and Team Formation
… links between collaborators, alongside Steiner tree problem solutions to form small teams to cover given tasks. Our framework not only considers size of the team but also how likely team members are to collaborate with each other. The framework is tested on sets of data from two different …
-
Two new algorithms for classical problems in computer science
… simple bookkeeping approximation solution to the Steiner tree problem in graphs. The problem presented deals with determining the shortest tree connecting Steiner nodes in a graph that has no direct connections between the Steiner nodes. Both algorithms are described and analyzed in detail with an …
-
The tabu ant colony optimizer and its application in an energy market
… the quadratic assignment problem (QAP), and the Steiner tree problem. In tree-shaped puzzles, the dual pheromone TabuACO was able to demonstrate a significant improvement in performance over a conventional ACO. As the amount of connectedness in the network increased, the dual pheromone TabuACO …
-
A constraint optimization framework for discovery of cellular signaling and regulatory networks
… interpret. We present a technique, based on the Steiner tree problem, that uses a probabilistic protein-protein interaction network and high confidence measurement and prediction of protein-DNA interactions, to determine how these hits are organized into functionally coherent pathways, revealing …
-
Spatial statistical-physical systems
… tends to an equilibrium that approximates the Steiner tree structure. For two- to four-anchor cases, we calculate the theoretical equilibrium configurations, and in particular for three and four anchors, the positions of the Steiner points. For one-anchor case, we consider a reversed model that …
-
Mobile backbone architecture for wireless ad-hoc networks : algorithms and performance analysis
… the Geometric Disk Cover (GDC) problem and the Steiner Tree Problem with Minimum Number of Steiner Points (STP-MSP). We prove that if these subproblems are solved separately by y- and 5-approximation algorithms, the approximation ratio of the joint solution is y1+6. Then, we focus on the two …
-
Multivariate methods for the statistical analysis of hyperdimensional high-content screening data
… in a network context using the Prize-Collecting Steiner Tree algorithm. This method offers superior performance over the current gold standard for the analysis of HC RNAi screens. A surprising finding from our analysis is that training sets of genes involved in complex biological phenomena used …
-
Generalized Group Steiner Trees
Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-05-01
-
Approximation algorithms for submodular optimization and graph problems
… and Shepherd on the connection between the treewidth of the graph and the existence of a good routing structure. Additionally, we initiate the study of integral throughput flow problems in directed graphs with symmetric demand pairs. We obtain a poly-logarithmic approximation with constant …
-
Vector-product-based Graphic Statics and Graphic Kinematics for moment-resisting structures
… and conclude with the introduction of the Steiner Tree as a potential topology for structural morphologies with efficient load paths. The research finishes with a synopsis, conclusions, and a projection of the developed methods onto the realm of architectural and structural engineering …
-
Layering principles for wireless networks
… simple class of computation strategies based on Steiner-tree packing (so-called computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, the performance of computation trees is known to be optimal when the underlying …
-
MATHEMATICAL PROGRAMMING ALGORITHMS FOR NETWORK OPTIMIZATION PROBLEMS
… constraints. - Knapsack Prize Collecting Steiner Tree Problem (KPCSTP): to implement a Column Generation algorithm for the MRWADC problem and for the HAP, we need also to solve the two corresponding pricing problems. These two problems are very similar, both of them require to find an …
-
Extremal problems on cycles, packing, and decomposition of graphs
… 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 S ⊆ V (G) to be j-edgeconnected in G if S lies in a single component of any graph obtained by …
-
Data mining and graph theory focused solutions to Smart Grid challenges
The Smart Grid represents a transition of the power and energy industry into a new era of improved efficiency, reliability, availability, and security, while contributing to economic and environmental health. However, several challenges must be addressed for real-life implementation of Smart Grids. …