{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T21:20:59Z","timestamp":1775942459779,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319126906","type":"print"},{"value":"9783319126913","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_21","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"268-282","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem"],"prefix":"10.1007","author":[{"given":"Ernst","family":"Althaus","sequence":"first","affiliation":[]},{"given":"Markus","family":"Blumenstock","sequence":"additional","affiliation":[]},{"given":"Alexej","family":"Disterhoft","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Hildebrandt","sequence":"additional","affiliation":[]},{"given":"Markus","family":"Krupp","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"21_CR1","unstructured":"Arora, S., Karakostas, G.: A 2 + $$\\epsilon $$ approximation algorithm for the k-MST problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201900, pp. 754\u2013759. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-642-38189-8_11","volume-title":"Facets of Combinatorial Optimization","author":"E \u00c1lvarez Miranda","year":"2013","unstructured":"\u00c1lvarez Miranda, E., Ljubi\u0107, I., Mutzel, P.: The maximum weight connected subgraph problem. In: J\u00fcnger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 245\u2013270. Springer, Heidelberg (2013)"},{"issue":"6","key":"21_CR3","doi-asserted-by":"publisher","first-page":"1355","DOI":"10.1016\/j.cor.2003.11.007","volume":"32","author":"C Blum","year":"2005","unstructured":"Blum, C., Blesa, M.J.: New metaheuristic approaches for the edge-weighted K-cardinality tree problem. Comput. Oper. Res. 32(6), 1355\u20131377 (2005)","journal-title":"Comput. Oper. Res."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities - an $${O}(n^{1\/4})$$ approximation for densest $$k$$-subgraph. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC \u201910, pp. 201\u2013210. ACM, New York (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"6","key":"21_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Backes, C., Rurainski, A., Klau, G.W., M\u00fcller, O., St\u00f6ckel, D., Gerasch, A., K\u00fcntzer, J., Maisel, D., Ludwig, N., Hein, M., Keller, A., Burtscher, H., Kaufmann, M., Meese, E., Lenhof, H.-P.: An integer linear programming approach for finding deregulated subgraphs in regulatory networks. Nucleic Acids Res. (2011)","DOI":"10.1093\/nar\/gkr1227"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jcss.1997.1542","volume":"58","author":"A Blum","year":"1999","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k-MST problem. J. Comput. Syst. Sci. 58(1), 101\u2013108 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Chimani, M., Kandyba, M., Ljubi\u0107, I., Mutzel, P.: Obtaining optimal K-cardinality trees fast. J. Exp. Algorithmics 14, 5:2.5\u20135:2.23 (2010)","DOI":"10.1145\/1498698.1537600"},{"issue":"D1","key":"21_CR9","doi-asserted-by":"publisher","first-page":"D472","DOI":"10.1093\/nar\/gkt1102","volume":"42","author":"D Croft","year":"2014","unstructured":"Croft, D., Mundo, A.F., Haw, R., Milacic, M., Weiser, J., Wu, G., Caudy, M., Garapati, P., Gillespie, M., Kamdar, M.R., Jassal, B., Jupe, S., Matthews, L., May, B., Palatnik, S., Rothfels, K., Shamovsky, V., Song, H., Williams, M., Birney, E., Hermjakob, H., Stein, L., D\u2019Eustachio, P.: The reactome pathway knowledgebase. Nucleic Acids Res. 42(D1), D472\u2013D477 (2014)","journal-title":"Nucleic Acids Res."},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jda.2012.04.016","volume":"16","author":"M Chimani","year":"2012","unstructured":"Chimani, M., Mutzel, P., Zey, B.: Improved Steiner tree algorithms for bounded treewidth. J. Discrete Algorithms 16, 67\u201378 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"21_CR11","unstructured":"Cohen, N.: Several graph problems and their LP formulation (explanatory supplement for the Sage graph library), July 2010. http:\/\/hal.inria.fr\/inria-00504914"},{"issue":"13","key":"21_CR12","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1093\/bioinformatics\/btn161","volume":"24","author":"MT Dittrich","year":"2008","unstructured":"Dittrich, M.T., Klau, G.W., Rosenwald, A., Dandekar, T., M\u00fcller, T.: Identifying functional modules in protein\u2013protein interaction networks: an integrated exact approach. Bioinformatics 24(13), 223\u2013231 (2008)","journal-title":"Bioinformatics"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1093\/bib\/bbn042","volume":"10","author":"I Dinu","year":"2009","unstructured":"Dinu, I., Potter, J.D., Mueller, T., Liu, Q., Adewale, A.J., Jhangri, G.S., Einecke, G., Famulski, K.S., Halloran, P., Yasui, Y.: Gene-set analysis and reduction. Briefings Bioinf. 10, 24\u201334 (2009)","journal-title":"Briefings Bioinf."},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-642-33718-5_28","volume-title":"Computer Vision \u2013 ECCV 2012","author":"A Fix","year":"2012","unstructured":"Fix, A., Chen, J., Boros, E., Zabih, R.: Approximate MRF inference using bounded treewidth subgraphs. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012, Part I. LNCS, vol. 7572, pp. 385\u2013398. Springer, Heidelberg (2012)"},{"issue":"1","key":"21_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/net.3230240103","volume":"24","author":"M Fischetti","year":"1994","unstructured":"Fischetti, M., Hamacher, H.W., J\u00f8rnsten, K., Maffioli, F.: Weighted k-cardinality trees: complexity and polyhedral structure. Networks 24(1), 11\u201321 (1994)","journal-title":"Networks"},{"issue":"3","key":"21_CR16","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 302\u2013309, October 1996","DOI":"10.1109\/SFCS.1996.548489"},{"issue":"13","key":"21_CR18","doi-asserted-by":"publisher","first-page":"i366","DOI":"10.1093\/bioinformatics\/btr228","volume":"27","author":"L Geistlinger","year":"2011","unstructured":"Geistlinger, L., Csaba, G., K\u00fcffner, R., Mulder, N., Zimmer, R.: From sets to graphs: towards a realistic enrichment analysis of transcriptomic systems. Bioinformatics 27(13), i366\u2013i373 (2011)","journal-title":"Bioinformatics"},{"key":"21_CR19","unstructured":"Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual (2014). http:\/\/www.gurobi.com\/documentation\/5.0\/reference-manual\/"},{"issue":"Suppl. 1","key":"21_CR20","doi-asserted-by":"publisher","first-page":"S233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","volume":"18","author":"T Ideker","year":"2002","unstructured":"Ideker, T., Ozier, O., Schwikowski, B., Siegel, A.F.: Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics 18(Suppl. 1), S233\u2013S240 (2002)","journal-title":"Bioinformatics"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36, 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"21_CR22","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley Longman Publishing Co. Inc., Boston (2005)"},{"key":"21_CR23","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E Lawler","year":"1976","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"key":"21_CR24","unstructured":"Ljubi\u0107, I.: Exact and memetic algorithms for two network design problems. Ph.D. thesis, Technische Universit\u00e4t Wien (2004). https:\/\/www.ads.tuwien.ac.at\/publications\/bib\/pdf\/ljubicPhD.pdf"},{"issue":"4","key":"21_CR25","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM 7(4), 326\u2013329 (1960)","journal-title":"J. ACM"},{"key":"21_CR26","unstructured":"Oracle corporation. Java Platform, Standard Edition 7 (2012). http:\/\/docs.oracle.com\/javase\/7\/docs\/api\/"},{"issue":"12","key":"21_CR27","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1016\/j.dam.2009.01.017","volume":"158","author":"FP Quint\u00e3o","year":"2010","unstructured":"Quint\u00e3o, F.P., da Cunha, A.S., Mateus, G.R., Lucena, A.: The k-cardinality tree problem: reformulations and lagrangian relaxation. Discrete Appl. Math. 158(12), 1305\u20131314 (2010)","journal-title":"Discrete Appl. Math."},{"key":"21_CR28","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.endm.2008.01.039","volume":"30","author":"FP Quint\u00e3o","year":"2008","unstructured":"Quint\u00e3o, F.P., da Cunha, A.S., Mateus, G.R.: Integer programming formulations for the k-cardinality tree problem. Electron. Notes Discrete Math. 30, 225\u2013230 (2008)","journal-title":"Electron. Notes Discrete Math."},{"issue":"43","key":"21_CR29","doi-asserted-by":"publisher","first-page":"15545","DOI":"10.1073\/pnas.0506580102","volume":"102","author":"A Subramanian","year":"2005","unstructured":"Subramanian, A., Tamayo, P., Mootha, V.K., Mukherjee, S., Ebert, B.L., Gillette, M.A., Paulovich, A., Pomeroy, S.L., Golub, T.R., Lander, E.S., Mesirov, J.P.: Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles. Proc. Natl Acad. Sci. U.S.A. 102(43), 15545\u201315550 (2005)","journal-title":"Proc. Natl Acad. Sci. U.S.A."},{"key":"21_CR30","unstructured":"Sathiamoorthy Subbarayan. TreeD: A Library for Tree Decomposition, July 2007. http:\/\/itu.dk\/people\/sathi\/treed\/"},{"issue":"9","key":"21_CR31","doi-asserted-by":"publisher","first-page":"e48","DOI":"10.1093\/nar\/gkn145","volume":"36","author":"X-MM Zhao","year":"2008","unstructured":"Zhao, X.-M.M., Wang, R.-S.S., Chen, L., Aihara, K.: Uncovering signal transduction networks from high-throughput data by integer linear programming. Nucleic Acids Res. 36(9), e48 (2008)","journal-title":"Nucleic Acids Res."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:25:58Z","timestamp":1747160758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}