Log in

Relevant bibliographies by topics / Steiner forest algorithm / Journal articles

Journal articles on the topic 'Steiner forest algorithm'

To see the other types of publications on this topic, follow the link: 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:

Consult the top 20 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

Feldman, Moran, Guy Kortsarz, and Zeev Nutov. "Improved approximation algorithms for Directed Steiner Forest." Journal of Computer and System Sciences 78, no. 1 (January 2012): 279–92. http://dx.doi.org/10.1016/j.jcss.2011.05.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Berman, Piotr, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. "Approximation algorithms for spanner problems and Directed Steiner Forest." Information and Computation 222 (January 2013): 93–107. http://dx.doi.org/10.1016/j.ic.2012.10.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Moldenhauer, Carsten. "Primal-dual approximation algorithms for Node-Weighted Steiner Forest on planar graphs." Information and Computation 222 (January 2013): 293–306. http://dx.doi.org/10.1016/j.ic.2012.10.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Cappa, Eduardo P., and Rodolfo JC Cantet. "Bayesian inference for normal multiple-trait individual-tree models with missing records via full conjugate Gibbs." Canadian Journal of Forest Research 36, no. 5 (May 1, 2006): 1276–85. http://dx.doi.org/10.1139/x06-024.

Full text

Abstract:

In forest genetics, restricted maximum likelihood (REML) estimation of (co)variance components from normal multiple-trait individual-tree models is affected by the absence of observations in any trait and individual. Missing records affect the form of the distribution of REML estimates of genetics parameters, or of functions of them, and the estimating equations are computationally involved when several traits are analysed. An alternative to REML estimation is a fully Bayesian approach through Markov chain Monte Carlo. The present research describes the use of the full conjugate Gibbs algorithm proposed by Cantet et al. (R.J.C. Cantet, A.N. Birchmeier, and J.P. Steibel. 2004. Genet. Sel. Evol. 36: 4964) to estimate (co)variance components in multiple-trait individual-tree models. This algorithm converges faster to the marginal posterior densities of the parameters than regular data augmentation from multivariate normal data with missing records. An expression to calculate the deviance information criterion for the selection of linear parameters in normal multiple-trait models is also given. The developments are illustrated by means of data from different crosses of two species of Pinus.

APA, Harvard, Vancouver, ISO, and other styles

15

Stückelberger, Jürg, Hans Rudolf Heinimann, and Woodam Chung. "Improved road network design models with the consideration of various link patterns and road design elements." Canadian Journal of Forest Research 37, no. 11 (November 2007): 2281–98. http://dx.doi.org/10.1139/x07-036.

Full text

Abstract:

The success of an automatic road network layout over steep terrain mainly depends on the model design. Most previous models have used a grid representation that considers only eight adjacent cells when evaluating feasible road links. Here, we present improved models and alignment constraints mapped on a mathematical graph for better designs that are more applicable under field conditions. We have refined the link pattern by considering up to 48 neighbouring cells and have introduced 16 directional classes per grid cell. Optimization techniques, such as shortest path, minimum spanning tree, and Steiner minimum tree algorithms, are used on the graph to derive a road network that is optimal in terms of its construction costs. These improved models have been applied to different mountainous project areas. Our results show that, by considering various link patterns and alignment constraints, one can determine more appropriate and cost-effective locations for road networks, especially in steep terrain.

APA, Harvard, Vancouver, ISO, and other styles

16

Saikia, Parikshit, Sushanta Karmakar, and Aris Pagourtzis. "Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree." Discrete Mathematics, Algorithms and Applications, September 26, 2020, 2150008. http://dx.doi.org/10.1142/s1793830921500087.

Full text

Abstract:

The Prize-collecting Steiner tree (PCST) problem is a generalization of the Steiner tree problem that finds applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms [D. Bienstock, M. X. Goemans, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem. Math. Program. 59 (1993) 413–420; M. X. Goemans and D. E. Williamson, A general approximation technique for constrained forest problems, SIAM J. Appl. Math. 24(2) (1995) 296–317; D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA ’00 (2000), pp. 760–769; A. Archer, M. Hossein Bateni and M. Taghi Hajiaghayi, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Comput. 40(2) (2011) 309–332] for solving the PCST problem. However, the problem has seen very little progress in the distributed setting; to the best of our knowledge, the only distributed algorithms proposed so far are due to Rossetti [N. G. Rossetti, A first attempt on the distributed prize-collecting Steiner tree problem, M.Sc. thesis, University of Iceland, Reykjavik (2015)]: one of them fails to guarantee a constant approximation factor while the other one is essentially centralized. In this work, first, we present a deterministic [Formula: see text] factor distributed approximation algorithm (D-PCST algorithm) that constructs a PCST for a given connected undirected graph of [Formula: see text] nodes with non-negative edge weights and non-negative prize value for each node. The D-PCST algorithm is based on the primal-dual method and uses a technique of preserving dual constraints in a distributed manner, without relying on knowledge of the global structure of the network. For an input graph [Formula: see text], the round and message complexities of the D-PCST algorithm in the CONGEST model are [Formula: see text] and [Formula: see text] respectively, where [Formula: see text] and [Formula: see text]. Furthermore, we modify the D-PCST algorithm and show that a [Formula: see text]-approximate PCST can be deterministically computed using [Formula: see text] rounds and [Formula: see text] messages in the CONGEST model, where [Formula: see text] is the unweighted diameter of [Formula: see text]. For networks with [Formula: see text], the modified D-PCST algorithm performs better than the original one in terms of the round complexity. Both the algorithms require [Formula: see text] bits of memory in each node, where [Formula: see text] is the maximum degree of a node in the graph.

APA, Harvard, Vancouver, ISO, and other styles

17

Jia, Xiao-Dan, Bo Hou, and Wen Liu. "An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties." Journal of the Operations Research Society of China, July 2, 2021. http://dx.doi.org/10.1007/s40305-021-00355-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Nagarajan, Viswanath, and Lily Wang. "Online Generalized Network Design Under (Dis)Economies of Scale." Mathematics of Operations Research, January 12, 2023. http://dx.doi.org/10.1287/moor.2022.1349.

Full text

Abstract:

We consider a general online network design problem in which a sequence of N requests arrive over time, each of which needs to use some subset of the available resources E. The cost incurred by a resource [Formula: see text] is some function fe of the total load [Formula: see text] on that resource. The objective is to minimize the total cost [Formula: see text]. We focus on cost functions that exhibit (dis)economies of scale. These functions are of the form [Formula: see text] if x > 0 (and zero if x = 0), in which the exponent [Formula: see text]. Optimization problems under these functions have received significant recent attention because of applications in energy-efficient computing. Our main result is a deterministic online algorithm with tight competitive ratio [Formula: see text] when αe is constant for all [Formula: see text]. This framework is applicable to a variety of network design problems in undirected and directed graphs, including multicommodity routing, Steiner tree/forest connectivity, and set connectivity. In fact, our online competitive ratio even matches the previous best (offline) approximation ratio. We also demonstrate the practical performance of our online algorithm on instances of multicommodity routing. Funding: This work was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1750127] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1940766].

APA, Harvard, Vancouver, ISO, and other styles

19

Ghalami, Laleh, and Daniel Grosu. "Approximation algorithms for Steiner forest: An experimental study." Networks, May 13, 2021. http://dx.doi.org/10.1002/net.22046.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Arici, M. Kaan, and Nurcan Tuncbag. "Performance Assessment of the Network Reconstruction Approaches on Various Interactomes." Frontiers in Molecular Biosciences 8 (October 5, 2021). http://dx.doi.org/10.3389/fmolb.2021.666705.

Full text

Abstract:

Beyond the list of molecules, there is a necessity to collectively consider multiple sets of omic data and to reconstruct the connections between the molecules. Especially, pathway reconstruction is crucial to understanding disease biology because abnormal cellular signaling may be pathological. The main challenge is how to integrate the data together in an accurate way. In this study, we aim to comparatively analyze the performance of a set of network reconstruction algorithms on multiple reference interactomes. We first explored several human protein interactomes, including PathwayCommons, OmniPath, HIPPIE, iRefWeb, STRING, and ConsensusPathDB. The comparison is based on the coverage of each interactome in terms of cancer driver proteins, structural information of protein interactions, and the bias toward well-studied proteins. We next used these interactomes to evaluate the performance of network reconstruction algorithms including all-pair shortest path, heat diffusion with flux, personalized PageRank with flux, and prize-collecting Steiner forest (PCSF) approaches. Each approach has its own merits and weaknesses. Among them, PCSF had the most balanced performance in terms of precision and recall scores when 28 pathways from NetPath were reconstructed using the listed algorithms. Additionally, the reference interactome affects the performance of the network reconstruction approaches. The coverage and disease- or tissue-specificity of each interactome may vary, which may result in differences in the reconstructed networks.

APA, Harvard, Vancouver, ISO, and other styles

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!