{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T00:05:11Z","timestamp":1759104311428,"version":"3.44.0"},"reference-count":40,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3735,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1016\/s0166-218x(02)00548-6","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T19:10:20Z","timestamp":1052766620000},"page":"511-540","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":15,"title":["Local search algorithms for the k-cardinality tree problem"],"prefix":"10.1016","volume":"128","author":[{"given":"Christian","family":"Blum","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Ehrgott","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"year":"1997","series-title":"Local Search in Combinatorial Optimization","author":"Aarts","key":"10.1016\/S0166-218X(02)00548-6_BIB1"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB2","doi-asserted-by":"crossref","unstructured":"S. Arora, Polynomial time approximation algorithms for Euclidean TSP and other geometric problems, in: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, IEEE Society Press, Los Alamitos, 1996, pp. 2\u201311.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Blum, S. Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, in: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 277\u2013283.","DOI":"10.1145\/225058.225139"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, SIAM J. Comput. 28(1) (1998) 254\u2013262.","DOI":"10.1137\/S009753979528826X"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, A. Vempala, A constant-factor approximation for the k-MST problem in the plane, in: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 294\u2013302.","DOI":"10.1145\/225058.225143"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB6","doi-asserted-by":"crossref","unstructured":"A. Blum, R. Ravi, A. Vempala, A constant-factor approximation for the k-MST problem, Comput. Systems Sci. 58 (1997) 101\u2013108.","DOI":"10.1006\/jcss.1997.1542"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB7","unstructured":"C. Blum, Optimality criteria and local search methods for node-weighted k-cardinality tree and subgraph problems, Master's Thesis, Department of Mathematics, University of Kaiserslautern, 1998 (in German)."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB8","unstructured":"C. Blum, M. Ehrgott, Local search algorithms for the k-cardinality tree problem, Technical Report, Department of Mathematics, University of Kaiserslautern, 1999, Report in Wirtschaftsmathematik No. 48, available at http:kluedo.ub.uni-kl.de\/Mathematik\/Quellen\/gelb_48.pdf."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB9","unstructured":"C. Blum, A. Roli, Metaheuristics in combinatorial optimization: overview and conceptual comparison, Technical Report, TR\/IRIDIA\/2001-13, IRIDIA, Universit\u00e9 Libre de Bruxelles, 2001."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB10","unstructured":"F. Catanas, Heuristics for the p-minimal spanning tree problem, Technical Report, Centre for Quantitative Finance, Imperial College, London, 1997."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB11","unstructured":"S.Y. Cheung, A. Kumar, Efficient quorumcast routing algorithms, in: Proceedings of INFOCOM 94, IEEE Society Press, Los Alamitos, 1994, pp. 840\u2013847."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB12","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1023\/A:1009647225748","article-title":"Solution of the cumulative assignment problem with a well-structured tabu search method","volume":"5","author":"Dell'Amico","year":"1999","journal-title":"J. Heuristics"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0898-1221(98)00150-3","article-title":"The computational complexity of the k-minimum spanning tree problem in graded matrices","volume":"36","author":"Dudas","year":"1998","journal-title":"Comput. Math. Appl"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB14","unstructured":"M. Ehrgott, Optimization problems in graphs under cardinality restrictions, Master's Thesis, Department of Mathematics, University of Kaiserslautern, 1992 (in German)."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB15","doi-asserted-by":"crossref","unstructured":"M. Ehrgott, J. Freitag, K_TREE \/ K_SUBGRAPH: a program package for minimal weighted K-cardinality-trees and -subgraphs, European J. Oper. Res. 93(1) (1996) 224\u2013225, Code available at http:\/\/www.mathematik.uni-kl.de\/~wwwwi\/WWWWI\/ORSEP\/contents.html.","DOI":"10.1016\/0377-2217(96)00084-7"},{"issue":"1","key":"10.1016\/S0166-218X(02)00548-6_BIB16","first-page":"87","article-title":"Heuristics for the k-cardinality tree and subgraph problem","volume":"14","author":"Ehrgott","year":"1997","journal-title":"Asia Pacific J. Oper. Res"},{"issue":"5","key":"10.1016\/S0166-218X(02)00548-6_BIB17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0925-7721(96)00021-1","article-title":"Faster geometric k-point MST approximation","volume":"8","author":"Eppstein","year":"1997","journal-title":"Comput. Geom"},{"issue":"4","key":"10.1016\/S0166-218X(02)00548-6_BIB18","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1287\/opre.42.4.688","article-title":"Computational complexity of some maximum average weight problems with precedence constraints","volume":"42","author":"Faigle","year":"1994","journal-title":"Oper. Res"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB19","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230240103","article-title":"Weighted k-cardinality trees","volume":"24","author":"Fischetti","year":"1994","journal-title":"Networks"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB20","unstructured":"L.R. Foulds, H.W. Hamacher, A new integer programming approach to (restricted) facilities layout problems allowing flexible facility shapes, Technical Report 1992\u20131993, Department of Management Science, University of Waikato, 1992."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB21","unstructured":"J. Freitag, Minimal k-cardinality trees, Master's Thesis, Department of Mathematics, University of Kaiserslautern, 1993 (in German)."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB22","doi-asserted-by":"crossref","unstructured":"N. Garg, A 3-approximation for the minimum tree spanning k vertices, in: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, IEEE Society Press, Los Alamitos, 1996, pp. 302\u2013309.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB23","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02523691","article-title":"An O(logk) approximation algorithm for the k minimum spanning tree problem in the plane","volume":"18","author":"Garg","year":"1997","journal-title":"Algorithmica"},{"issue":"3","key":"10.1016\/S0166-218X(02)00548-6_BIB24","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu search","volume":"1","author":"Glover","year":"1989","journal-title":"ORSA J. Comput"},{"issue":"1","key":"10.1016\/S0166-218X(02)00548-6_BIB25","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","article-title":"Tabu search","volume":"2","author":"Glover","year":"1990","journal-title":"ORSA J. Comput"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB26","unstructured":"H.W. Hamacher, K. Joernsten, Optimal relinquishment according to the Norwegian petrol law: a combinatorial optimization approach, Technical Report no. 7\/93, Norwegian School of Economics and Business Administration, Bergen, 1993."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB27","unstructured":"P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming, Talk presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(99)00435-X","article-title":"A framework for the description of evolutionary algorithms","volume":"126","author":"Hertz","year":"2000","journal-title":"European J. Oper. Res"},{"issue":"2","key":"10.1016\/S0166-218X(02)00548-6_BIB29","first-page":"9","article-title":"Tabu search for weighted k-cardinality trees","volume":"14","author":"Joernsten","year":"1997","journal-title":"Asia Pacific J. Oper. Res"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB30","unstructured":"F. Maffioli, Finding a best subtree of a tree, Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, 1991."},{"issue":"2","key":"10.1016\/S0166-218X(02)00548-6_BIB31","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/S0895480194266331","article-title":"Spanning trees\u2014short or small","volume":"9","author":"Marathe","year":"1996","journal-title":"SIAM J. Discrete Math"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB32","unstructured":"J.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1996, pp. 402\u2013408."},{"issue":"4","key":"10.1016\/S0166-218X(02)00548-6_BIB33","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","article-title":"Guillotine subdivisions approximate polygonal subdivisions","volume":"28","author":"Mitchell","year":"1999","journal-title":"SIAM J. Comput"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB34","unstructured":"P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: toward memetic algorithms, Technical Report Caltech Concurrent Computation Program 826, California Institute of Technology, Pasadena, California, USA, 1989."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB35","series-title":"Foundations of Genetic Algorithms","first-page":"316","article-title":"Evolution in time and space\u2014the parallel genetic algorithm","author":"M\u00fchlenbein","year":"1991"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB36","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF02125421","article-title":"Metaheuristics","volume":"63","author":"Osman","year":"1996","journal-title":"Ann. Oper. Res"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB37","unstructured":"A.B. Philpott, N.C. Wormald, On the optimal extraction of ore from an open-cast mine, University of Auckland, New Zealand, 1997."},{"key":"10.1016\/S0166-218X(02)00548-6_BIB38","unstructured":"S. Rajagopalan, V.V. Vazirani, Logarithmic approximation of minimum weight k trees, unpublished manuscript, 1995."},{"issue":"4","key":"10.1016\/S0166-218X(02)00548-6_BIB39","first-page":"303","article-title":"Computing maximum valued regions","volume":"10","author":"Woeginger","year":"1992","journal-title":"Acta Cybernet"},{"key":"10.1016\/S0166-218X(02)00548-6_BIB40","unstructured":"A. Zelikovsky, D. Lozevanu, Minimal and bounded trees, in: Tezele Cong. XVIII Acad. Romano-Americane, Kishinev, 1993, pp. 25\u201326."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02005486?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02005486?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T11:57:18Z","timestamp":1759060638000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02005486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":40,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["S0166218X02005486"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00548-6","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2003,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Local search algorithms for the k-cardinality tree problem","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0166-218X(02)00548-6","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2003 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}