Academic literature on the topic 'Steiner forest algorithm'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
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"
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 textLai, 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 textGao, 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 textRavi, 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 textNorman, 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 textDinitz, 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 textHan, 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 textDing, 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 textHu, 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 textChekuri, 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 textDissertations / Theses on the topic "Steiner forest algorithm"
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 textIn 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.
Gupta, Shubham. "Building Networks in the Face of Uncertainty." Thesis, 2011. http://hdl.handle.net/10012/6140.
Full textBook chapters on the topic "Steiner forest algorithm"
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 textAkhmedov, 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 textVazirani, 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 textSchä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 textSchä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 textCygan, 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 textBereg, 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 textDing, 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 textCohen, 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 textSuzuki, 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 textConference papers on the topic "Steiner forest algorithm"
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 textGupta, 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 textFeldman, 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 textChlamtáč, 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 textEisenstat, 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 textGhalami, 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 textLOMOV, 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