Relevant bibliographies by topics / Steiner forest algorithm

Academic literature on the topic 'Steiner forest algorithm'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Steiner forest algorithm.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Steiner forest algorithm"

1

Zhang, Peng, and Mingji Xia. "An approximation algorithm to the k-Steiner Forest problem." Theoretical Computer Science 410, no. 11 (March 2009): 1093–98. http://dx.doi.org/10.1016/j.tcs.2008.10.033.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Lai, Katherine, Carla Gomes, Michael Schwartz, Kevin McKelvey, David Calkin, and Claire Montgomery. "The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (August 4, 2011): 1357–64. http://dx.doi.org/10.1609/aaai.v25i1.7809.

Full text
Abstract:
The conservation of wildlife corridors between existing habitat preserves is important for combating the effects of habitat loss and fragmentation facing species of concern. We introduce the Steiner Multigraph Problem to model the problem of minimum-cost wildlife corridor design for multiple species with different landscape requirements. This problem can also model other analogous settings in wireless and social networks. As a generalization of Steiner forest, the goal is to find a minimum-cost subgraph that connects multiple sets of terminals. In contrast to Steiner forest, each set of terminals can only be connected via a subset of the nodes. Generalizing Steiner forest in this way makes the problem NP-hard even when restricted to two pairs of terminals. However, we show that if the node subsets have a nested structure, the problem admits a fixed-parameter tractable algorithm in the number of terminals. We successfully test exact and heuristic solution approaches on a wildlife corridor instance for wolverines and lynx in western Montana, showing that though the problem is computationally hard, heuristics perform well, and provably optimal solutions can still be obtained.
APA, Harvard, Vancouver, ISO, and other styles
3

Gao, Jiawen, Suogang Gao, Wen Liu, Weili Wu, Ding-Zhu Du, and Bo Hou. "An approximation algorithm for the k-generalized Steiner forest problem." Optimization Letters 15, no. 4 (March 24, 2021): 1475–83. http://dx.doi.org/10.1007/s11590-021-01727-y.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ravi, R. "A primal-dual approximation algorithm for the Steiner forest problem." Information Processing Letters 50, no. 4 (May 1994): 185–89. http://dx.doi.org/10.1016/0020-0190(94)00034-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Norman, Utku, and A. Ercument Cicek. "ST-Steiner: a spatio-temporal gene discovery algorithm." Bioinformatics 35, no. 18 (February 13, 2019): 3433–40. http://dx.doi.org/10.1093/bioinformatics/btz110.

Full text
Abstract:
AbstractMotivationWhole exome sequencing (WES) studies for autism spectrum disorder (ASD) could identify only around six dozen risk genes to date because the genetic architecture of the disorder is highly complex. To speed the gene discovery process up, a few network-based ASD gene discovery algorithms were proposed. Although these methods use static gene interaction networks, functional clustering of genes is bound to evolve during neurodevelopment and disruptions are likely to have a cascading effect on the future associations. Thus, approaches that disregard the dynamic nature of neurodevelopment are limited.ResultsHere, we present a spatio-temporal gene discovery algorithm, which leverages information from evolving gene co-expression networks of neurodevelopment. The algorithm solves a prize-collecting Steiner forest-based problem on co-expression networks, adapted to model neurodevelopment and transfer information from precursor neurodevelopmental windows. The decisions made by the algorithm can be traced back, adding interpretability to the results. We apply the algorithm on ASD WES data of 3871 samples and identify risk clusters using BrainSpan co-expression networks of early- and mid-fetal periods. On an independent dataset, we show that incorporation of the temporal dimension increases the predictive power: predicted clusters are hit more and show higher enrichment in ASD-related functions compared with the state-of-the-art.Availability and implementationThe code is available at http://ciceklab.cs.bilkent.edu.tr/st-steiner.Supplementary informationSupplementary data are available at Bioinformatics online.
APA, Harvard, Vancouver, ISO, and other styles
6

Dinitz, Michael, Guy Kortsarz, and Zeev Nutov. "Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights." ACM Transactions on Algorithms 13, no. 3 (August 9, 2017): 1–16. http://dx.doi.org/10.1145/3077581.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Han, Lu, Da-Chuan Xu, Dong-Lei Du, and Chen-Chen Wu. "A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem." Journal of the Operations Research Society of China 5, no. 2 (May 2, 2017): 219–31. http://dx.doi.org/10.1007/s40305-017-0164-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ding, Wei, and Ke Qiu. "A 2-approximation algorithm and beyond for the minimum diameter k-Steiner forest problem." Theoretical Computer Science 840 (November 2020): 1–15. http://dx.doi.org/10.1016/j.tcs.2019.12.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Hu, Yuxuan, Tao Peng, Lin Gao, and Kai Tan. "CytoTalk: De novo construction of signal transduction networks using single-cell transcriptomic data." Science Advances 7, no. 16 (April 2021): eabf1356. http://dx.doi.org/10.1126/sciadv.abf1356.

Full text
Abstract:
Single-cell technology enables study of signal transduction in a complex tissue at unprecedented resolution. We describe CytoTalk for de novo construction of cell type–specific signaling networks using single-cell transcriptomic data. Using an integrated intracellular and intercellular gene network as the input, CytoTalk identifies candidate pathways using the prize-collecting Steiner forest algorithm. Using high-throughput spatial transcriptomic data and single-cell RNA sequencing data with receptor gene perturbation, we demonstrate that CytoTalk has substantial improvement over existing algorithms. To better understand plasticity of signaling networks across tissues and developmental stages, we perform a comparative analysis of signaling networks between macrophages and endothelial cells across human adult and fetal tissues. Our analysis reveals an overall increased plasticity of signaling networks across adult tissues and specific network nodes that contribute to increased plasticity. CytoTalk enables de novo construction of signal transduction pathways and facilitates comparative analysis of these pathways across tissues and conditions.
APA, Harvard, Vancouver, ISO, and other styles
10

Chekuri, Chandra, Alina Ene, and Ali Vakilian. "Node-weighted Network Design in Planar and Minor-closed Families of Graphs." ACM Transactions on Algorithms 17, no. 2 (June 2021): 1–25. http://dx.doi.org/10.1145/3447959.

Full text
Abstract:
We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Steiner forest algorithm"

1

Tan, Kunlun. "On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1123.

Full text
Abstract:
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 $G$ that spans all terminals in $R$. The goal is to compute a feasible Steiner tree of smallest cost. In this thesis we will focus on approximation algorithms for this problem: a $c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance.

In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms.

Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2.

Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm.

The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.
APA, Harvard, Vancouver, ISO, and other styles
2

Gupta, Shubham. "Building Networks in the Face of Uncertainty." Thesis, 2011. http://hdl.handle.net/10012/6140.

Full text
Abstract:
The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We 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 cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Steiner forest algorithm"

1

Markarian, Christine. "An Optimal Algorithm for Online Prize-Collecting Node-Weighted Steiner Forest." In Lecture Notes in Computer Science, 214–23. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94667-2_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Akhmedov, Murodzhon, Alexander LeNail, Francesco Bertoni, Ivo Kwee, Ernest Fraenkel, and Roberto Montemanni. "A Fast Prize-Collecting Steiner Forest Algorithm for Functional Analyses in Biological Networks." In Integration of AI and OR Techniques in Constraint Programming, 263–76. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-59776-8_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Vazirani, Vijay V. "Steiner Forest." In Approximation Algorithms, 197–211. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-662-04565-7_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Schäfer, Guido. "Steiner Forest." In Encyclopedia of Algorithms, 2099–102. New York, NY: Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_402.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Schäfer, Guido. "Steiner Forest." In Encyclopedia of Algorithms, 897–900. Boston, MA: Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_402.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Cygan, Marek, Guy Kortsarz, and Zeev Nutov. "Steiner Forest Orientation Problems." In Algorithms – ESA 2012, 361–72. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33090-2_32.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bereg, Sergey, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. "Colored Non-crossing Euclidean Steiner Forest." In Algorithms and Computation, 429–41. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-48971-0_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ding, Wei, and Ke Qiu. "Minimum Diameter k-Steiner Forest." In Algorithmic Aspects in Information and Management, 1–11. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-04618-7_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Cohen, Nachshon, and Zeev Nutov. "Approximating Steiner Trees and Forests with Minimum Number of Steiner Points." In Approximation and Online Algorithms, 95–106. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-18263-6_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Suzuki, Hitoshi, Chiseko Yamanaka, and Takao Nishizeki. "Parallel algorithms for finding Steiner forests in planar graphs." In Algorithms, 458–67. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990. http://dx.doi.org/10.1007/3-540-52921-7_95.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Steiner forest algorithm"

1

Ghalami, Laleh, and Daniel Grosu. "A Parallel Approximation Algorithm for the Steiner Forest Problem." In 2022 30th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). IEEE, 2022. http://dx.doi.org/10.1109/pdp55904.2022.00016.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gupta, Anupam, and Amit Kumar. "Greedy Algorithms for Steiner Forest." In STOC '15: Symposium on Theory of Computing. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2746539.2746590.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Feldman, Moran, Guy Kortsarz, and Zeev Nutov. "Improved Approximating Algorithms for Directed Steiner Forest." In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009. http://dx.doi.org/10.1137/1.9781611973068.100.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chlamtáč, Eden, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. "Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974782.34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Eisenstat, David, Philip Klein, and Claire Mathieu. "An efficient polynomial-time approximation scheme for Steiner forest in planar graphs." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.53.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Ghalami, Laleh, and Daniel Grosu. "A Family of Fast Parallel Greedy Algorithms for the Steiner Forest Problem." In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 2022. http://dx.doi.org/10.1109/ipdpsw55747.2022.00130.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

LOMOV, STEPAN V., JEONYOON LEEJEONYOON LEE, BRIAN L. WARDLE, NIKITA A. GUDKOV, ISKANDER S. AKHATOV, and SERGEY G. ABAIMOV. "COMPUTATIONAL DESCRIPTION OF THE GEOMETRY OF ALIGNED CARBON NANOTUBES IN POLYMER NANOCOMPOSITES." In Thirty-sixth Technical Conference. Destech Publications, Inc., 2021. http://dx.doi.org/10.12783/asc36/35861.

Full text
Abstract:
The paper considers nanocomposites, reinforced with aligned carbon nanotubes (A- CNTs). Nominally aligned, the CNTs in the forest are wavy, which has important consequences in downgraded mechanical properties, and influences electric and thermal performance. The most detailed geometrical model of A-CNTs was proposed by Stein and Wardle (Nanotechnology, 27:035701, 2015). It creates a centerline trajectory of a CNT in steps, each step defining a section of the CNT, growing in the alignment direction with certain deviations. The paper, starting from this framework, formulates a model of the CNT geometry, which is based on the concept of correlation length of the CNT waviness and maximum admissible CNT curvature and torsion. The value of the maximum curvature can be linked to the buckling criteria for CNTs, or derived from ab initio and finite element modelling. It is used as a limiting factor for the growth, defining the waviness and tortuosity of the CNTs. The CNTs in the forest are placed in a random non-regular way, using Voronoi tessellation. The full paper includes investigation of the proposed algorithm for several values of the CNT volume fraction (in the range 0.5%…8%), the dependency of the modelled geometry on the curvature, and the apparent twist of the CNT centerlines. The modelling results are compared with experimental observations in 3D TEM imaging.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Steiner forest algorithm' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography