{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:55:31Z","timestamp":1725486931439},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540728443"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72845-0_29","type":"book-chapter","created":{"date-parts":[[2007,6,26]],"date-time":"2007-06-26T12:51:37Z","timestamp":1182862297000},"page":"379-392","source":"Crossref","is-referenced-by-count":2,"title":["A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem"],"prefix":"10.1007","author":[{"given":"Markus","family":"Behle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"J\u00fcnger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frauke","family":"Liers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"29_CR1","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1016\/j.dam.2005.06.011","volume":"154","author":"R. Andrade","year":"2006","unstructured":"Andrade, R., Lucena, A., Maculan, N.: Using lagrangian dual information to generate degree constrained spanning trees. Discrete Applied Mathematics\u00a0154(5), 703\u2013717 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR2","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1287\/opre.22.2.383","volume":"22","author":"L.R. Arnold","year":"1974","unstructured":"Arnold, L.R., Bellmore, M.: A bounding minimization problem for primal integer programming. Operations Research\u00a022, 383\u2013392 (1974)","journal-title":"Operations Research"},{"key":"29_CR3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1287\/opre.22.1.137","volume":"22","author":"L.R. Arnold","year":"1974","unstructured":"Arnold, L.R., Bellmore, M.: A generated cut for primal integer programming. Operations Research\u00a022, 137\u2013143 (1974)","journal-title":"Operations Research"},{"key":"29_CR4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1287\/opre.22.1.129","volume":"22","author":"L.R. Arnold","year":"1974","unstructured":"Arnold, L.R., Bellmore, M.: Iteration skipping in primal integer programming. Operations Research\u00a022, 129\u2013136 (1974)","journal-title":"Operations Research"},{"key":"29_CR5","unstructured":"Barahona, F., Titan, H.: Max mean cuts and max cuts. In: Combinatorial Optimization in Science and Technology, pp. 30\u201345 (1991)"},{"issue":"2","key":"29_CR6","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1002\/1097-0037(200103)37:2<74::AID-NET2>3.0.CO;2-E","volume":"37","author":"L. Caccetta","year":"2001","unstructured":"Caccetta, L., Hill, S.P.: A branch and cut method for the degree-constrained minimum spanning tree problem. Networks\u00a037(2), 74\u201383 (2001)","journal-title":"Networks"},{"key":"29_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/10556789408805564","volume":"3","author":"C. Simone De","year":"1994","unstructured":"De Simone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Optimization Methods and Software\u00a03, 195\u2013214 (1994)","journal-title":"Optimization Methods and Software"},{"key":"29_CR8","first-page":"69","volume-title":"Combinatorial Structures and their Applications","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and their Applications, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math.\u00a0Programming\u00a01, 127\u2013136 (1971)","journal-title":"Math.\u00a0Programming"},{"key":"29_CR10","unstructured":"Eisenbrand, F., Rinaldi, G., Ventura, P.: 0\/1 optimization and 0\/1 primal separation are equivalent. In: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms, SODA \u201902, pp. 920\u2013926 (2002)"},{"key":"29_CR11","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1287\/opre.16.4.727","volume":"16","author":"F. Glover","year":"1968","unstructured":"Glover, F.: A new foundation for a simplified primal integer programming algorithm. Operations Research\u00a016, 727\u2013740 (1968)","journal-title":"Operations Research"},{"key":"29_CR13","first-page":"273","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"M.X. Goemans","year":"2006","unstructured":"Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 273\u2013282. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"29_CR14","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L.: Handbook of Combinatorics, In: Combinatorial Optimization (chapter), vol. 2, pp. 1541\u20131597. North Holland (1995)"},{"issue":"2","key":"29_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Papadimitriou, C.H.: On linear characterizations of combinatorial optimization problems. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York pp. 1\u20139 (1980)","DOI":"10.1109\/SFCS.1980.29"},{"issue":"2","key":"29_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1109\/4235.850653","volume":"4","author":"J.D. Knowles","year":"2000","unstructured":"Knowles, J.D., Corne, D.W.: A new evolutionary approach to the degree-constrained minimum spanning tree problem. IEEE Transactions on Evolutionary Computation\u00a04(2), 125\u2013134 (2000)","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1023\/A:1011977126230","volume":"7","author":"M. Krishnamoorthy","year":"2001","unstructured":"Krishnamoorthy, M., Ernst, A.T., Sharaiha, Y.M.: Comparison of algorithms for the degree constrained minimum spanning tree. Journal of Heuristics\u00a07, 587\u2013611 (2001)","journal-title":"Journal of Heuristics"},{"issue":"1","key":"29_CR19","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematics Society\u00a07(1), 48\u201350 (1956)","journal-title":"Proceedings of the American Mathematics Society"},{"issue":"1","key":"29_CR20","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s001860200200","volume":"56","author":"A.N. Letchford","year":"2002","unstructured":"Letchford, A.N., Lodi, A.: Primal cutting plane algorithms revisited. Mathematical Methods of Operations Research\u00a056(1), 67\u201381 (2002)","journal-title":"Mathematical Methods of Operations Research"},{"key":"29_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"A.N. Letchford","year":"2003","unstructured":"Letchford, A.N., Lodi, A.: An augment-and-branch-and-cut framework for mixed 0-1 programming. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570. Springer, Heidelberg (2003)"},{"issue":"3","key":"29_CR22","first-page":"209","volume":"1","author":"A.N. Letchford","year":"2003","unstructured":"Letchford, A.N., Lodi, A.: Primal separation algorithms. 4OR\u00a01(3), 209\u2013224 (2003)","journal-title":"4OR"},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics\u00a05, 54\u201366 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"29_CR24","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0305-0548(80)90022-2","volume":"7","author":"S.C. Narula","year":"1980","unstructured":"Narula, S.C., Ho, C.A.: Degree-constrained minimum spanning tree. Computers & Operations Research\u00a07, 239\u2013249 (1980)","journal-title":"Computers & Operations Research"},{"key":"29_CR25","first-page":"307","volume-title":"Polyhedral computations (chapter)","author":"M.W. Padberg","year":"1985","unstructured":"Padberg, M.W., Gr\u00f6tschel, M.: The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. In: Polyhedral computations (chapter), pp. 307\u2013360. Wiley, Chichester (1985)"},{"key":"29_CR26","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120888","volume":"12","author":"M.W. Padberg","year":"1980","unstructured":"Padberg, M.W., Hong, S.: On the symmetric travelling salesman problem: a computational study. Mathematical Programming Study\u00a012, 78\u2013107 (1980)","journal-title":"Mathematical Programming Study"},{"key":"29_CR27","unstructured":"Padberg, M.W., Rao, M.R.: The russian method for linear programming III: Bounded integer programming. Technical Report 81-39, Graduate School of Business and Administration, New York University (1981)"},{"key":"29_CR28","first-page":"511","volume":"17","author":"M.W. Padberg","year":"1983","unstructured":"Padberg, M.W., Wolsey, L.A.: Trees and cuts. Annals of Discrete Mathematics\u00a017, 511\u2013517 (1983)","journal-title":"Annals of Discrete Mathematics"},{"key":"29_CR29","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. Prim","year":"1957","unstructured":"Prim, R.: Shortest connection networks and some generalizations. Bell System Technical Journal\u00a036, 1389\u20131401 (1957)","journal-title":"Bell System Technical Journal"},{"key":"29_CR30","unstructured":"Raidl, G.R.: personal communication"},{"key":"29_CR31","doi-asserted-by":"crossref","unstructured":"Raidl, G.R.: An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the 2000 IEEE Congress on Evolutionary Computation, vol. 1, pp. 104\u2013111 (2000)","DOI":"10.1109\/CEC.2000.870282"},{"issue":"1-2","key":"29_CR32","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(01)00255-4","volume":"118","author":"C.C. Ribeiro","year":"2002","unstructured":"Ribeiro, C.C., Souza, M.C.: Variable neighborhood search for the degree-constrained minimum spanning tree problem. Discrete Applied Mathematics\u00a0118(1-2), 43\u201354 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0305-0548(85)90032-2","volume":"12","author":"M. Savelsbergh","year":"1985","unstructured":"Savelsbergh, M., Volgenant, T.: Edge exchanges in the degree-constrained minimum spanning tree problem. Computers & Operations Research\u00a012, 341\u2013348 (1985)","journal-title":"Computers & Operations Research"},{"key":"29_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/3-540-60313-1_164","volume-title":"Algorithms - ESA \u201995","author":"A.S. Schulz","year":"1995","unstructured":"Schulz, A.S., Weismantel, R., Ziegler, G.M.: 0\/1 integer programming: Optimization and augmentation are equivalent. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 473\u2013483. Springer, Heidelberg (1995)"},{"key":"29_CR35","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF03398508","volume":"34","author":"S. Sharma","year":"1997","unstructured":"Sharma, S., Sharma, B.: New technique for solving primal all-integer linear programming. Opsearch\u00a034, 62\u201368 (1997)","journal-title":"Opsearch"},{"key":"29_CR36","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0377-2217(89)90169-0","volume":"39","author":"A. Volgenant","year":"1989","unstructured":"Volgenant, A.: A lagrangean approach to the degree-constrained minimum spanning tree problem. European Journal of Operational Research\u00a039, 325\u2013331 (1989)","journal-title":"European Journal of Operational Research"},{"key":"29_CR37","volume-title":"Integer Programming","author":"L.A. Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Wiley-Interscience, New York, USA (1998)"},{"key":"29_CR38","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1287\/opre.16.4.750","volume":"16","author":"R.D. Young","year":"1968","unstructured":"Young, R.D.: A simplified primal (all-integer) integer programming algorithm. Operations Research\u00a016, 750\u2013782 (1968)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72845-0_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:05:49Z","timestamp":1605762349000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72845-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540728443"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72845-0_29","relation":{},"subject":[]}}