{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:00:32Z","timestamp":1778601632996,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB 531"],"award-info":[{"award-number":["SFB 531"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            Given an undirected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with edge weights and a positive integer number\n            <jats:italic>k<\/jats:italic>\n            , the\n            <jats:italic>k<\/jats:italic>\n            -cardinality tree problem consists of finding a subtree\n            <jats:italic>T<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            with exactly\n            <jats:italic>k<\/jats:italic>\n            edges and the minimum possible weight. Many algorithms have been proposed to solve this NP-hard problem, resulting in mainly heuristic and metaheuristic approaches.\n          <\/jats:p>\n          <jats:p>In this article, we present an exact ILP-based algorithm using directed cuts. We mathematically compare the strength of our formulation to the previously known ILP formulations of this problem, and show the advantages of our approach. Afterwards, we give an extensive study on the algorithm's practical performance compared to the state-of-the-art metaheuristics.<\/jats:p>\n          <jats:p>In contrast to the widespread assumption that such a problem cannot be efficiently tackled by exact algorithms for medium and large graphs (between 200 and 5,000 nodes), our results show that our algorithm not only has the advantage of proving the optimality of the computed solution, but also often outperforms the metaheuristic approaches in terms of running time.<\/jats:p>","DOI":"10.1145\/1498698.1537600","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":9,"title":["Obtaining optimal\n            <i>k<\/i>\n            -cardinality trees fast"],"prefix":"10.1145","volume":"14","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Kandyba","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivana","family":"Ljubi\u0107","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA'00)","author":"Arora S.","unstructured":"Arora , S. and Karakostas , G . 2000. A (2+&euro;)-approximation algorithm for the k-MST problem . In Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA'00) . ACM Press, 754--759. Arora, S. and Karakostas, G. 2000. A (2+&euro;)-approximation algorithm for the k-MST problem. In Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA'00). ACM Press, 754--759."},{"key":"e_1_2_1_2_1","unstructured":"Blesa M. J. and Xhafa F. 2000. A C++ implementation of tabu search for k-cardinality tree problem based on generic programming and component reuse. In Net.ObjectDays 2000 Tagungsband. Net.ObjectDays-Forum Erfurt Germany 648--652.  Blesa M. J. and Xhafa F. 2000. A C++ implementation of tabu search for k-cardinality tree problem based on generic programming and component reuse. In Net.ObjectDays 2000 Tagungsband. Net.ObjectDays-Forum Erfurt Germany 648--652."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237992"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143997.1144092"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.11.005"},{"key":"e_1_2_1_6_1","unstructured":"Blum C. and Blesa M. 2003. KCTLIB -- a library for the edge-weighted k-cardinality tree problem. http:\/\/iridia.ulb.ac.be\/~cblum\/kctlib\/.  Blum C. and Blesa M. 2003. KCTLIB -- a library for the edge-weighted k-cardinality tree problem. http:\/\/iridia.ulb.ac.be\/~cblum\/kctlib\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11494669_4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2003.11.007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00548-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.07.061"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'04)","author":"Bui T. N.","unstructured":"Bui , T. N. and Sundarraj , G . 2004. Ant system for the k-cardinality tree problem . In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'04) . Springer, Berlin, 36--47. Bui, T. N. and Sundarraj, G. 2004. Ant system for the k-cardinality tree problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'04). Springer, Berlin, 36--47."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009180"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85097-7_18"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA'07)","author":"Chimani M.","unstructured":"Chimani , M. , Kandyba , M. , and Mutzel , P . 2007. A new ILP formulation for 2-root-connected prize-collecting Steiner networks . In Proceedings of the European Symposium on Algorithms (ESA'07) . Springer, Berlin, 681--692. Chimani, M., Kandyba, M., and Mutzel, P. 2007. A new ILP formulation for 2-root-connected prize-collecting Steiner networks. In Proceedings of the European Symposium on Algorithms (ESA'07). Springer, Berlin, 681--692."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Integer Programmingand Combinatorial Optimization (IPCO '01)","author":"Chudak F. A.","unstructured":"Chudak , F. A. , Roughgarden , T. , and Williamson , D. P . 2001. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation . In Proceedings of the Integer Programmingand Combinatorial Optimization (IPCO '01) . Springer, Berlin, 60--70. Chudak, F. A., Roughgarden, T., and Williamson, D. P. 2001. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. In Proceedings of the Integer Programmingand Combinatorial Optimization (IPCO '01). Springer, Berlin, 60--70."},{"key":"e_1_2_1_16_1","first-page":"214","article-title":"K TREE\/K SUBGRAPH: a program package for minimal weighted k-cardinality tree subgraph problem","volume":"1","author":"Ehrgott M.","year":"1996","unstructured":"Ehrgott , M. and Freitag , J. 1996 . K TREE\/K SUBGRAPH: a program package for minimal weighted k-cardinality tree subgraph problem . Eur. J. Operational Res. 1 , 93, 214 -- 225 . Ehrgott, M. and Freitag, J. 1996. K TREE\/K SUBGRAPH: a program package for minimal weighted k-cardinality tree subgraph problem. Eur. J. Operational Res. 1, 93, 214--225.","journal-title":"Eur. J. Operational Res."},{"key":"e_1_2_1_17_1","first-page":"87","article-title":"Heuristics for the k-cardinality tree and subgraph problem","volume":"14","author":"Ehrgott M.","year":"1997","unstructured":"Ehrgott , M. , Freitag , J. , Hamacher , H. , and Maffioli , F. 1997 . Heuristics for the k-cardinality tree and subgraph problem . Asia-Pac J. Operational Res. 14 , 1, 87 -- 114 . Ehrgott, M., Freitag, J., Hamacher, H., and Maffioli, F. 1997. Heuristics for the k-cardinality tree and subgraph problem. Asia-Pac J. Operational Res. 14, 1, 87--114.","journal-title":"Asia-Pac J. Operational Res."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240103"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.1073"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875522"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060650"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230104"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_24_1","first-page":"9","article-title":"Tabu search for weighted k-cardinality trees","volume":"14","author":"Joernsten K.","year":"1997","unstructured":"Joernsten , K. and Lokketangen , A. 1997 . Tabu search for weighted k-cardinality trees . Asia-Pac. J. Operational Res. 14 , 9 -- 26 . Joernsten, K. and Lokketangen, A. 1997. Tabu search for weighted k-cardinality trees. Asia-Pac. J. Operational Res. 14, 9--26.","journal-title":"Asia-Pac. J. Operational Res."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O"},{"key":"e_1_2_1_26_1","unstructured":"Koch T. Martin A. and Voss S. 2003. SteinLib&quest;an updated library on Steiner tree problems in graphs. http:\/\/elib.zib.de\/steinlib.  Koch T. Martin A. and Voss S. 2003. SteinLib&quest;an updated library on Steiner tree problems in graphs. http:\/\/elib.zib.de\/steinlib."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0660-x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194266331"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Metaheuristics International Conference (MIC'01)","author":"Rossetti I.","unstructured":"Rossetti , I. , de Arag\u00e3o , M. P. , Ribeiro , C. , Uchoa , E. , and Werneck , R. F . 2001. New benchmark instances for the Steiner problem in graphs . In Proceedings of the Metaheuristics International Conference (MIC'01) . Elsevier Science Ltd., Oxford, UK, 557--561. Rossetti, I., de Arag\u00e3o, M. P., Ribeiro, C., Uchoa, E., and Werneck, R. F. 2001. New benchmark instances for the Steiner problem in graphs. In Proceedings of the Metaheuristics International Conference (MIC'01). Elsevier Science Ltd., Oxford, UK, 557--561."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170102"},{"key":"e_1_2_1_32_1","unstructured":"Spec. 2006. Standard performance evaluation corporation. http:\/\/www.spec.org\/.  Spec. 2006. Standard performance evaluation corporation. http:\/\/www.spec.org\/."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(03)00073-X"},{"key":"e_1_2_1_34_1","volume-title":"Integer Programming","author":"Wolsey L. A.","unstructured":"Wolsey , L. A. 1998. Integer Programming . Wiley-Interscience , New York . Wolsey, L. A. 1998. Integer Programming. Wiley-Interscience, New York."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1537600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":33,"alternative-id":["10.1145\/1498698.1537600"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1537600","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}