A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems

References

• 11th DIMACS Challenge (2014) Steiner tree problems. http://dimacs11.zib.de.Google Scholar
• Álvarez-Miranda E, Ljubić I, Mutzel P (2013) The maximum weight connected subgraph problem. Jünger M, Reinelt G, eds. Facets of Combinatorial Optimization—Festschrift for Martin Grötschel (Springer, Berlin), 245–270.Crossref, Google Scholar
• Backes C, Rurainski A, Klau G, Müller O, Stöckel D, Gerasch A, Küntzer Jet al. (2011) An integer linear programming approach for finding deregulated subgraphs in regulatory networks. Nucleic Acids Res. 40(6):e43.Crossref, Google Scholar
• Balakrishnan A, Magnanti TL, Wong RT (1989) A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. 37(5):716–740.Link, Google Scholar
• Camerini PM, Fratta L, Maffioli F (1979) A note on finding optimum branchings. Networks 9(4):309–312.Crossref, Google Scholar
• Chen CY, Grauman K (2012) Efficient activity detection with max-subgraph search. IEEE Conf. Comput. Vision Pattern Recognition, Providence, RI, 1274–1281.Google Scholar
• de Aragão MP, Werneck RF (2002) On the implementation of MST-based heuristics for the Steiner problem in graphs. Mount DM, Stein C, eds. Algorithm Engrg. Experiments ALENEX 2002. Lecture Notes in Computer Science, Vol. 2409 (Springer, Berlin), 1–15.Google Scholar
• Dittrich MT, Klau GW, Rosenwald A, Dandekar T, Müller T (2008) Identifying functional modules in protein–protein interaction networks: An integrated exact approach. Bioinformatics 24(13):i223–i231.Crossref, Google Scholar
• Duin CW (1993) Steiner’s problem in graphs. PhD thesis, University of Amsterdam.Google Scholar
• Duin CW, Volgenant A (1989) Reduction tests for the Steiner problem in graphs. Networks 19(5):549–567.Crossref, Google Scholar
• Edmonds J (1967) Optimum branchings. J. Res. National Bureau Standards B 71(4):233–240.Crossref, Google Scholar
• El-Kebir M, Klau GW (2014) Solving the maximum-weight connected subgraph problem to optimality. Technical report, 11th DIMACS Challenge Workshop, http://dimacs11.zib.de/workshop/ElKebirKlau.pdf.Google Scholar
• Faust K, Croes D, van Helden J (2011) Prediction of metabolic pathways from genome-scale metabolic networks. Biosystems 105(2):109–121.Crossref, Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017) Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Programming Comput. 9(2):203–229.Crossref, Google Scholar
• Fu ZH, Hao JK (2014) Knowledge guided tabu search for the prize collecting Steiner tree problem in graphs. Technical report, 11th DIMACS Challenge Workshop, http://dimacs11.zib.de/workshop/FuHao.pdf.Google Scholar
• Fu ZH, Hao JK (2017) Swap-vertex based neighborhood for Steiner tree problems. Math. Programming Comput. 9(2):297–320.Crossref, Google Scholar
• Gamrath G, Koch T, Maher SJ, Rehfeldt D, Shinano Y (2017) SCIP-jack—A solver for STP and variants with parallelization extensions. Math. Programming Comput. 9(2):231–296.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• Hegde C, Indyk P, Schmidt L (2014) A fast, adaptive variant of the Goemans-Williamson scheme for the prize-collecting Steiner tree problem. Technical report, 11th DIMACS Challenge Workshop, http://people.csail.mit.edu/ludwigs/papers/dimacs14_fastpcst.pdf.Google Scholar
• Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: Theory and practice. Shmoys DB, ed. Sympos. Discrete Algorithms (ACM/SIAM, Philadelphia), 760–769.Google Scholar
• Koch T, Martin A (1998) Solving Steiner tree problems in graphs to optimality. Networks 32(3):207–232.Crossref, Google Scholar
• Koch T, Martin A, Voß S (2000) SteinLib: An updated library on Steiner tree problems in graphs. Technical report, Zuse Institute Berlin, http://steinlib.zib.de.Google Scholar
• Lengauer T, Tarjan RE (1979) A fast algorithm for finding dominators in a flowgraph. ACM Trans. Programming Languages Systems 1(1):121–141.Crossref, Google Scholar
• Ljubić I, Weiskircher R, Pferschy U, Klau GW, Mutzel P, Fischetti M (2006) An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Programming105(2–3):427–449.Crossref, Google Scholar
• Pajor T, Uchoa E, Werneck RF (2017) A robust and scalable algorithm for the Steiner problem in graphs. Math. Programming Comput., ePub ahead of print September 4, https://doi.org/10.1007/s12532-017-0123-4.Google Scholar
• Polzin T, Daneshmand SV (2001) Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112(1):263–300.Crossref, Google Scholar
• Ramanathan S (1996) Multicast tree generation in networks with asymmetric links. IEEE/ACM Trans. Networking 4(4):558–568.Crossref, Google Scholar
• Rehfeldt D, Koch T, Maher SJ (2016) Reduction techniques for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. Technical report, Zuse Institute Berlin, https://opus4.kobv.de/opus4-zib/files/6042/PcMwReductions.pdf.Google Scholar
• Takahashi H, Matsuyama A (1980) An approximate solution for the Steiner problem in graphs. Math. Japonica 24(6):573–577.Google Scholar
• Uchoa E (2006) Reduction tests for the prize-collecting Steiner problem. Oper. Res. Lett. 34(4):437–444.Crossref, Google Scholar
• Wong RT (1984) A dual ascent approach for Steiner tree problems on a directed graph. Math. Programming 28(3):271–287.Crossref, Google Scholar