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 14 of 14 for “"steiner forest"”.
-
Parallel Algorithms For Steiner Forest
The Steiner Forest Problem is one of the fundamental combinatorial optimization problemsin operations research and computer science. Its applications range from network design to computational biology. Given an undirected graph with non-negative weights for edges and a set of pairs of vertices …
-
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 …
-
FROM HARDNESS TO STRUCTURE: ALGORITHMIC INSIGHTS FROM SAT, DIVERSITY, AND CONNECTIVITY
… Connectivity, encompassing the Prize-Collecting Steiner Forest (PCSF) and Steiner Forest (SFP) problems, the thesis develops new algorithmic frameworks grounded in combinatorial structure and local refinement. For PCSF, it presents the first deterministic and purely combinatorial 2-approximation …
-
Optimizing resource allocation in computational sustainability: Models, algorithms and tools
… contagion. We also formulate a new variant of Steiner Forest network design, called the budget-constrained prize-collecting Steiner forest, and prove that this optimization problem possesses a specific combinatorial structure, restricted supermodularity, that allows us to design highly …
-
USING THE PRIZE-COLLECTING STEINER SYSTEM TO DISSECT GENOMIC REGULATORY NETWORKS FROM HETEROGENEOUS DATA
… interaction). The Prize-Collecting Steiner Tree (PCST) problem finds a connected subtree of a network in which a sum of costs for edges in the subtree and prizes for vertices not in the subtree is minimised. The Prize-Collecting Steiner Forest (PCSF) problem finds multiple subtrees …
-
Prize-Collecting Network Design
… algorithm for the prizecollecting Steiner forest problem using iterative rounding. In the second setting, we give an O(log n)-competitive algorithm for the constrained forest problem with 0-1 proper connectivity requirement functions using the primal-dual method and extend our …
-
Online Steiner Cover Problems in Hypergraphs
The online Steiner cover problem in hypergraphs (\treePN) is a generalization of the online Steiner tree problem in graphs. An edge-weighted hypergraph $H = (V, E, w)$ is given offline and a set of terminal vertices $R\subseteq V$ is requested sequentially online. Upon receiving each request …
-
Cost Sharing and Approximation
… problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.
-
Unraveling the Proteome of Endothelial Cells Latently Infected with KSHV Reveals Reliance on Peroxisome Lipid Metabolism and Redox Regulation
… prediction of many pathways activated by KSHV. A Steiner forest analysis utilizing a database of protein-protein interactions was employed in this step. From the set of predicted activated pathways, I validated two novel pathways that are activated during KSHV latency, peroxisome biogenesis and …
-
Host-pathogen cartography: predictive network mapping of Ebola virus-host cell interactions reveals mechanisms of viral control of the cell
… algorithms including the Prize-Collecting Steiner Forest network analysis. We investigated whether network topology from the resulting network maps could predict the identification of key genes regulating viral replication. While we found no significant relationship between network topology …
-
Network-Design Problems in Graphs and on the Plane
… In the k-Colored Non-Crossing Euclidean Steiner Forest problem, we are given an integer k and a finite set of points in the plane where each point has one of k colors. For every color, we are asked for a drawing that connects all the points of the same color. The constraint is that …
-
Directed Graphs: Fixed-Parameter Tractability & Beyond
… connectivity problems such as Strongly Connected Steiner Subgraph and Directed Steiner Forest when parameterized by the number of terminals/terminal pairs. We design new optimal XP algorithms for the aforementioned problems, and also prove matching lower bounds for existing XP algorithms. Most of …
-
Primal-Dual Techniques for Online Algorithms and Mechanisms
… different variants of online matching and online Steiner connectivity, via online dual techniques. Although there are many generic tools for solving an optimization problem in the offline paradigm, in comparison, much less is known for tackling online problems. The main focus of this work is to …
-
Building Networks in the Face of Uncertainty
… also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low …