{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T19:41:46Z","timestamp":1770320506060,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2001,11,1]],"date-time":"2001-11-01T00:00:00Z","timestamp":1004572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,11,1]],"date-time":"2001-11-01T00:00:00Z","timestamp":1004572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Heuristics"],"published-print":{"date-parts":[[2001,11]]},"DOI":"10.1023\/a:1011977126230","type":"journal-article","created":{"date-parts":[[2002,12,23]],"date-time":"2002-12-23T11:29:09Z","timestamp":1040642949000},"page":"587-611","source":"Crossref","is-referenced-by-count":84,"title":["Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree"],"prefix":"10.1007","volume":"7","author":[{"given":"Mohan","family":"Krishnamoorthy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas T.","family":"Ernst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yazid M.","family":"Sharaiha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"358748_CR1","first-page":"567","volume":"2","author":"R.K. Ahuja","year":"1995","unstructured":"Ahuja, R.K., J.B. Orlin, and A. Tiwari. (1995). \u201cA Greedy Genetic Algorithm for the Quadratic Assignment Problem.\u201d In Proceedings, The Sixth International Conference on Manufacturing Engineering. Melbourne, Australia, 29 Nov.\u20131 Dec. 1995, Vol. 2, pp.567\u2013575.","journal-title":"Proceedings, The Sixth International Conference on Manufacturing Engineering"},{"key":"358748_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S. (1996). \u201cPolynomial Time Approximation Scheme for Euclidean tsp and Other Geometric Problems.\u201d In Proceedings 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, pp. 2\u201311.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"358748_CR3","volume-title":"Approximate Solution of NP-Hard Optimization Problems","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, and M. Protasi. (1999).Approximate Solution of NP-Hard Optimization Problems.Berlin: Springer-Verlag."},{"issue":"11","key":"358748_CR4","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"J.E. Beasley","year":"1990","unstructured":"Beasley, J.E. (1990). \u201cOr-Library: Distributing Test Problems by Electronic Mail.\u201d Journal of the Operational Research Society41(11),1069\u20131072.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"358748_CR5","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1016\/0167-8191(95)00010-0","volume":"22","author":"B. Boldon","year":"1996","unstructured":"Boldon, B., N. Deo, and N. Kumar. (1996). \u201cMinimum-Weight Degree-Constrained Spanning Tree Problem: Heuristics and Implementation on an Simd Parallel Machine.\u201dParallel Computing 22(3), 369\u2013382.","journal-title":"Parallel Computing"},{"issue":"3\u20134","key":"358748_CR6","first-page":"209","volume":"8","author":"N. Collins","year":"1998","unstructured":"Collins, N., R. Eglese, and B. Golden. (1998) \u201cSimulated Annealing: An Annotated Bibliography.\u201d American Journal of Mathematical and Management Sciences8(3\u20134),209\u2013307.","journal-title":"American Journal of Mathematical and Management Sciences"},{"key":"358748_CR7","volume-title":"Metaheuristics: Theory and Applications","author":"G. Craig","year":"1996","unstructured":"Craig. G., M. Krishnamoorthy, and M. Palaniswami. (1996). \u201cComparison of Heuristic Algorithms for the Degree Constrained Minimum Spanning Tree.\u201d In I.H. Osman and J.P. Kelly (eds.), Metaheuristics: Theory and Applications.Boston: Kluwer."},{"key":"358748_CR8","unstructured":"Cresenzi, P. and V. Kann. (1995). \u201cA Compendium of np Optimization Problems.\u201d Technical report, Universit\u00e0 di Roma \u201cLa Sapienza.\u201d http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html."},{"key":"358748_CR9","volume-title":"Handbook of Genetic Algorithms","author":"L. Davis","year":"1991","unstructured":"Davis, L. (1991). Handbook of Genetic Algorithms. New york: Van Nostrand."},{"key":"358748_CR10","first-page":"194","volume":"450","author":"N. Deo","year":"1997","unstructured":"Deo, N. and N. Kumar. (1997). \u201cComputation of Constrained Spanning Trees: A Unified Approach.\u201d Network Optimization450,194\u2013220.","journal-title":"Network Optimization"},{"key":"358748_CR11","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N. (1983). \u201cData Structures for On-Line Updating of Minimum Spanning Trees.\u201d In Proceedings of the 15th Annual ACM Symposium of the Theory of Computing.Boston, MA.","DOI":"10.1145\/800061.808754"},{"issue":"4","key":"358748_CR12","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N. (1985). \u201cData Structures for On-Line Updating of Minimum Spanning Trees.\u201d SIAM J. Comput. 14(4), 781\u2013798.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"358748_CR13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/net.3230080304","volume":"8","author":"H.N. Gabow","year":"1978","unstructured":"Gabow, H.N. (1978). \u201cGood Algorithm for Smallest Spanning Trees with a Degree Constraint,\u201d Networks8(3), 201\u2013208.","journal-title":"Networks"},{"key":"358748_CR14","volume-title":"Computers and Intractability, A Guide to the Theory of NP\u2013Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability, A Guide to the Theory of NP\u2013Completeness. San Francisco: Freeman."},{"key":"358748_CR15","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1002\/net.3230120402","volume":"12","author":"B. Gavish","year":"1982","unstructured":"Gavish, B. (1982). \u201cTopological Design of Centralized Computer Networks\u2014Formulations and Algorithms.\u201d Networks12,355\u2013377.","journal-title":"Networks"},{"issue":"12","key":"358748_CR16","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1109\/TCOM.1985.1096250","volume":"33","author":"B. Gavish","year":"1985","unstructured":"Gavish, B. (1985). \u201cAugmented Lagrangean Based Algorithms for Centralized Network Design.\u201dIEEE Transactions on Communications33(12),1247\u20131257.","journal-title":"IEEE Transactions on Communications"},{"key":"358748_CR17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0377-2217(92)90204-M","volume":"58","author":"B. Gavish","year":"1992","unstructured":"Gavish, B. (1992). \u201cTopological Design of Centralized Computer Networks\u2014the Overall Design Problem.\u201dEuropean Journal of Operations Research58,149\u2013172.","journal-title":"European Journal of Operations Research"},{"key":"358748_CR18","doi-asserted-by":"crossref","unstructured":"Gen, M., G. Zhou, and M. Takayama. (1998). \u201cA Comparative Study of Tree Encodings on Spanning Tree Problems.\u201d IEEE Conference on Evolutionary Computation.","DOI":"10.1109\/ICEC.1998.699114"},{"key":"358748_CR19","doi-asserted-by":"crossref","first-page":"1276","DOI":"10.1287\/mnsc.40.10.1276","volume":"40","author":"M. Gendreau","year":"1994","unstructured":"Gendreau, M., A. Hertz, and G. Laporte. (1994). \u201cA Tabu Search Heuristic for the Vehicle Routing Problem.\u201d Management Science40,1276\u20131290.","journal-title":"Management Science"},{"key":"358748_CR20","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF00175357","volume":"4","author":"F. Glover","year":"1994","unstructured":"Glover, F. (1994). \u201cGenetic Algorithms and Scatter Search: Unsuspected Potentials.\u201dStatistics and Computing4, 131\u2013140.","journal-title":"Statistics and Computing"},{"key":"358748_CR21","volume-title":"Genetic Algorithms in Search, Optimization, and Machine Learning","author":"D.E. Goldberg","year":"1989","unstructured":"Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning.Reading, MA: Addison-Wesley."},{"key":"358748_CR22","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"Held, M. and R.M. Karp. (1970). \u201cThe Travelling-Salesman Problem and Minimum Spanning Trees.\u201d Operations Research18,1138\u20131162.","journal-title":"Operations Research"},{"key":"358748_CR23","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"Held, M. and K.R.M. (1971). \u201cThe Travelling\u2013Salesman Problem and Minimum Spanning Trees: Part II.\u201dMathematical Programming1,6\u201325.","journal-title":"Mathematical Programming"},{"key":"358748_CR24","volume-title":"Adaptation in Natural and Artificial Systems","author":"J.H. Holland","year":"1975","unstructured":"Holland, J.H. (1975). Adaptation in Natural and Artificial Systems.Cambridge, MA: MIT Press."},{"key":"358748_CR25","unstructured":"Kawatra, R. (1997). \u201cLagrangean Based Heuristic for the Degree Constrained Minimal Spanning Tree.\u201d In Proceedings of the Annual Meeting of the decision Sciences Institute. Nov. 22\u201325, San Diego, USA."},{"key":"358748_CR26","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1137\/S0097539794264585","volume":"25","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., B. Raghavachari, and N. oung. (1996). \u201cLowDegree Spanning Trees of SmallWeight.\u201dSIAM Journal on Computing25,355\u2013368.","journal-title":"SIAM Journal on Computing"},{"key":"358748_CR27","first-page":"70","volume-title":"A Seminar on Graph Theory","author":"J.W. Moon","year":"1967","unstructured":"Moon, J.W. (1967). \u201cVarious Proofs of Cayley's Formula for Counting Trees.\u201d In F. Harary (ed.), A Seminar on Graph Theory. New York: Holt, Rinehart and Winston. pp.70\u201378."},{"key":"358748_CR28","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0305-0548(80)90022-2","volume":"7","author":"S.C. Narula","year":"1980","unstructured":"Narula, S.C. and C.A. Ho. (1980). \u201cDegree Constrained Minimum Spanning Tree.\u201dComputers and Operations Research7,239\u2013249.","journal-title":"Computers and Operations Research"},{"key":"358748_CR29","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF02125421","volume":"63","author":"I.H. Osman","year":"1996","unstructured":"Osman, I.H. and G. Laporte. (1996). \u201cMetaheuristcs: A Bibliography.\u201dAnnals of Operations Research63, 513\u2013623.","journal-title":"Annals of Operations Research"},{"key":"358748_CR30","doi-asserted-by":"crossref","unstructured":"Palmer, C.E. and A. Kershenbaum. (1994). \u201cRepresenting Trees in Genetic Algorithms.\u201d Technical report, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, 1994.","DOI":"10.1109\/ICEC.1994.349921"},{"key":"358748_CR31","volume-title":"Modern Heuristic Techniques for Combinatorial Problems","year":"1993","unstructured":"Reeves, C.R. (ed.). (1993). Modern Heuristic Techniques for Combinatorial Problems.Oxford: Blackwell Scientific Publications."},{"issue":"1","key":"358748_CR32","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/101.17235","volume":"5","author":"R.A. Rutenbar","year":"1989","unstructured":"Rutenbar, R.A. (1989). \u201cSimulated Annealing Algorithms: An Overview.\u201d IEEE Circuits and Devices Magazine 5(1),19\u201326.","journal-title":"IEEE Circuits and Devices Magazine"},{"issue":"4","key":"358748_CR33","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/0305-0548(85)90032-2","volume":"12","author":"M. Savelsbergh","year":"1985","unstructured":"Savelsbergh, M. and T. Volgenant. (1985). \u201cEdge Exchanges in the Degree-Constrained Minimum Spanning Tree Problem.\u201dComputers and Operations Research12(4),341\u2013348.","journal-title":"Computers and Operations Research"},{"key":"358748_CR34","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F","volume":"3","author":"Y.M. Sharaiha","year":"1997","unstructured":"Sharaiha, Y.M., M. Gendreau, G. Laporte, and I.H. Osman. (1997). \u201cA Tabu Search Algorithm for the Capacitated Shortest Spanning Tree.\u201d Networks3, 161\u2013171.","journal-title":"Networks"},{"key":"358748_CR35","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF02156630","volume":"63","author":"R.H. Storer","year":"1996","unstructured":"Storer, R.H., S.W. Flanders, and S.D. Wu. (1996). \u201cProblem Space Local Search for Number Partitioning.\u201dThe Annals of Operations Research63,465\u2013487.","journal-title":"The Annals of Operations Research"},{"issue":"10","key":"358748_CR36","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1287\/mnsc.38.10.1495","volume":"38","author":"R.H. Storer","year":"1992","unstructured":"Storer, R.H., S.D. Wu, and R. Vaccari. (1992). \u201cNew Search Spaces for Sequencing Problems with Application to Job Shop Scheduling.\u201d Management Science38(10),1495\u20131509.","journal-title":"Management Science"},{"key":"358748_CR37","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0377-2217(89)90169-0","volume":"39","author":"A. Volgenant","year":"1989","unstructured":"Volgenant, A. (1989). \u201cA Langrangean Approach to the Degree Constrained Minimum Spanning Tree Problem.\u201d European Journal of Operational Research39,325\u2013331.","journal-title":"European Journal of Operational Research"},{"key":"358748_CR38","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/0377-2217(83)90161-3","volume":"12","author":"A. Volgenant","year":"1983","unstructured":"Volgenant, A. and R. Jonker. (1983). \u201cThe Symmetric Travelling Salesman Problem and Edge Exchanges in Minimum 1\u2013Trees.\u201dEuropean Journal of Operational Research12,394\u2013403.","journal-title":"European Journal of Operational Research"},{"key":"358748_CR39","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/BF01609023","volume":"15","author":"Y. Yamamoto","year":"1978","unstructured":"Yamamoto, Y. (1978). \u201cThe Held\u2013Karp Algorithm and Degree\u2013Constrained Minimum 1\u2013Trees.\u201dMathematical Programming15,228\u2013231.","journal-title":"Mathematical Programming"},{"issue":"2","key":"358748_CR40","first-page":"156","volume":"3","author":"G. Zhou","year":"1997","unstructured":"Zhou, G. and M. Gen. (1997). \u201cApproach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithms.\u201d Engineering Design and Automation3(2),156\u2013165.","journal-title":"Engineering Design and Automation"},{"key":"358748_CR41","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<91::AID-NET3>3.0.CO;2-F","volume":"30","author":"G. Zhou","year":"1997","unstructured":"Zhou, G. and M. Gen. (1997). \u201cA Note on Genetic Algorithms for Degree Constrained Minimum Spanning Tree Problems.\u201d Networks30,105\u2013109.","journal-title":"Networks"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011977126230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1011977126230\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011977126230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T10:58:12Z","timestamp":1747652292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1011977126230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,11]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,11]]}},"alternative-id":["358748"],"URL":"https:\/\/doi.org\/10.1023\/a:1011977126230","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,11]]}}}