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"”.

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

    wayne-thes Repository record for Parallel Algorithms For Steiner Forest (opens in a new tab)

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

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

    maryland Repository record for FROM HARDNESS TO STRUCTURE: ALGORITHMIC INSIGHTS FROM SAT, DIVERSITY, AND CONNECTIVITY (opens in a new tab)

  4. 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 …

    gatech Repository record for Optimizing resource allocation in computational sustainability: Models, algorithms and tools (opens in a new tab)

  5. 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 …

    nus Repository record for USING THE PRIZE-COLLECTING STEINER SYSTEM TO DISSECT GENOMIC REGULATORY NETWORKS FROM HETEROGENEOUS DATA (opens in a new tab) Download file for USING THE PRIZE-COLLECTING STEINER SYSTEM TO DISSECT GENOMIC REGULATORY NETWORKS FROM HETEROGENEOUS DATA (opens in a new tab)

  6. 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 …

    cornell Repository record for Prize-Collecting Network Design (opens in a new tab)

  7. 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 …

    concordia Download PDF for Online Steiner Cover Problems in Hypergraphs (opens in a new tab)

  8. Cost Sharing and Approximation

    … problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.

    cornell Repository record for Cost Sharing and Approximation (opens in a new tab)

  9. 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 …

    washington Repository record for Unraveling the Proteome of Endothelial Cells Latently Infected with KSHV Reveals Reliance on Peroxisome Lipid Metabolism and Redox Regulation (opens in a new tab)

  10. 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 …

    bu Repository record for Host-pathogen cartography: predictive network mapping of Ebola virus-host cell interactions reveals mechanisms of viral control of the cell (opens in a new tab)

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

    wurz-thes Repository record for Network-Design Problems in Graphs and on the Plane (opens in a new tab)

  12. 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 …

    maryland Repository record for Directed Graphs: Fixed-Parameter Tractability & Beyond (opens in a new tab)

  13. 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 …

    maryland Repository record for Primal-Dual Techniques for Online Algorithms and Mechanisms (opens in a new tab)

  14. 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 …

    waterloo Repository record for Building Networks in the Face of Uncertainty (opens in a new tab)