{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:32Z","timestamp":1740122372851,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,8,9]],"date-time":"2017-08-09T00:00:00Z","timestamp":1502236800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Laboratoire d\u2019Informatique, de Robotique et de Micro\u00e9lectronique de Montpellier."},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008222","name":"Universit\u00e9 de Montpellier","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008222","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-017-0159-4","type":"journal-article","created":{"date-parts":[[2017,8,9]],"date-time":"2017-08-09T10:02:59Z","timestamp":1502272979000},"page":"789-811","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["ILP formulation of the degree-constrained minimum spanning hierarchy problem"],"prefix":"10.1007","volume":"36","author":[{"given":"Massinissa","family":"Merabet","sequence":"first","affiliation":[]},{"given":"Miklos","family":"Molnar","sequence":"additional","affiliation":[]},{"given":"Sylvain","family":"Durand","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"issue":"10","key":"159_CR1","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1109\/49.887907","volume":"18","author":"M Ali","year":"2000","unstructured":"Ali M, Deogun JS (2000) Power-efficient design of multicast wavelength-routed networks. IEEE J Sel Areas Commun 18(10):1852\u20131862. doi:\n                        10.1109\/49.887907","journal-title":"IEEE J Sel Areas Commun"},{"key":"159_CR2","doi-asserted-by":"crossref","unstructured":"Bauer F, Varma A (1995) Degree-constrained multicasting in point-to-point networks. In: Proceedings of IEEE INFOCOM, pp 369\u2013376","DOI":"10.1109\/INFCOM.1995.515897"},{"issue":"3","key":"159_CR3","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s10589-007-9120-2","volume":"42","author":"R Cerulli","year":"2009","unstructured":"Cerulli R, Gentili M, Iossa A (2009) Bounded-degree spanning tree problems: models and new algorithms. Comput Optim Appl 42(3):353\u2013370","journal-title":"Comput Optim Appl"},{"issue":"1","key":"159_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01589353","volume":"20","author":"N Christofides","year":"1981","unstructured":"Christofides N, Mingozzi A, Toth P (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math Programm 20(1):255\u2013282. doi:\n                        10.1007\/BF01589353","journal-title":"Math Programm"},{"issue":"1","key":"159_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math Programm 33(1):1\u201327. doi:\n                        10.1007\/BF01582008","journal-title":"Math Programm"},{"key":"159_CR6","unstructured":"Deo N, Hakimi L (1968) The shortest generalized hamiltonian tree. In: 6th annual allerton conference, Illinois, pp 879\u2013888"},{"issue":"3","key":"159_CR7","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0377-2217(85)90151-1","volume":"21","author":"B Fleischmann","year":"1985","unstructured":"Fleischmann B (1985) A cutting plane procedure for the travelling salesman problem on road networks. Eur J Oper Res 21(3):307\u2013317","journal-title":"Eur J Oper Res"},{"key":"159_CR8","unstructured":"Furer M, Raghavachari B (1992) Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, SODA \u201992, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 317\u2013324"},{"key":"159_CR9","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York"},{"key":"159_CR10","doi-asserted-by":"crossref","unstructured":"Goemans M (2006) Minimum bounded degree spanning trees. In: 47th annual IEEE symposium on foundations of computer science, 2006. FOCS \u201906, pp 273\u2013282","DOI":"10.1109\/FOCS.2006.48"},{"issue":"1","key":"159_CR11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0012-365X(94)90235-6","volume":"132","author":"P Hell","year":"1994","unstructured":"Hell P, Zhu X (1994) Homomorphisms to oriented paths. Discrete Math 132(1):107\u2013114","journal-title":"Discrete Math"},{"issue":"5","key":"159_CR12","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1287\/mnsc.20.5.814","volume":"20","author":"D Klingman","year":"1974","unstructured":"Klingman D, Napier A, Stutz J (1974) A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Manage Sci 20(5):814\u2013821","journal-title":"Manage Sci"},{"issue":"6","key":"159_CR13","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1023\/A:1011977126230","volume":"7","author":"M Krishnamoorthy","year":"2001","unstructured":"Krishnamoorthy M, Ernst AT, Sharaiha YM (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heuristics 7(6):587\u2013611","journal-title":"J Heuristics"},{"issue":"1","key":"159_CR14","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48\u201350","journal-title":"Proc Am Math Soc"},{"key":"159_CR15","unstructured":"Makhorin A (2009), GNU Linear Programming Kit (GLPK) v 4.38, gnu project Edition"},{"key":"159_CR16","unstructured":"Molnar M (2008a) Hierarchies for constrained partial spanning problems in graphs, Technical report PI-1900"},{"key":"159_CR17","unstructured":"Molnar M (2008b) Hierarchies to solve constrained spanning problem, Private communication"},{"key":"159_CR18","doi-asserted-by":"publisher","unstructured":"Molnar M, Durand S, Merabet M (2014) Approximation of the degree-constrained minimum spanning hierarchies. In: Halldorsson MM (ed) Structural information and communication complexity: 21st international colloquium, SIROCCO 2014, Takayama, Japan. Proceedings, Springer International Publishing, pp 96\u2013107. doi:\n                        10.1007\/978-3-319-09620-9","DOI":"10.1007\/978-3-319-09620-9"},{"issue":"4","key":"159_CR19","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1093\/comjnl\/10.4.374","volume":"10","author":"AK Obruca","year":"1968","unstructured":"Obruca AK (1968) Spanning tree manipulation and the travelling salesman problem. Comput J 10(4):374\u2013377","journal-title":"Comput J"},{"issue":"1","key":"159_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/net.3230040105","volume":"4","author":"CS Orloff","year":"1974","unstructured":"Orloff CS (1974) A fundamental problem in vehicle routing. Networks 4(1):35\u201364. doi:\n                        10.1002\/net.3230040105","journal-title":"Networks"},{"issue":"1","key":"159_CR21","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0166-218X(00)00318-8","volume":"112","author":"T Polzin","year":"2001","unstructured":"Polzin T, Daneshmand SV (2001) A comparison of Steiner tree relaxations. Discrete Appl Math 112(1):241\u2013261 (combinatorial optimization symposium, selected papers)","journal-title":"Discrete Appl Math"},{"key":"159_CR22","doi-asserted-by":"crossref","unstructured":"Ravi R, Marathe MV, Ravi SS, Rosenkrantz DJ, Hunt III HB (1993) Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, STOC \u201993, ACM, New York, pp 438\u2013447","DOI":"10.1145\/167088.167209"},{"key":"159_CR23","doi-asserted-by":"crossref","unstructured":"Ravi R, Marathe M, Ravi S et al (2001) Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31:58","DOI":"10.1007\/s00453-001-0038-2"},{"key":"159_CR24","doi-asserted-by":"crossref","unstructured":"Singh M, Lau LC (2007) Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the thirty-ninth annual ACM symposium on theory of computing, STOC \u201907, ACM, New York, pp 661\u2013670","DOI":"10.1145\/1250790.1250887"},{"key":"159_CR25","doi-asserted-by":"publisher","unstructured":"Singh M, Zenklusen R (2016) k-trails: Recognition, complexity, and approximations. In: Louveaux Q, Skutella M (eds) Integer programming and combinatorial optimization: 18th international conference, IPCO 2016, Li\u00e8ge, Belgium, 1\u20133 June 2016, Proceedings, Springer International Publishing, Cham, pp 114\u2013125. doi:\n                        10.1007\/978-3-319-33461-510","DOI":"10.1007\/978-3-319-33461-510"},{"issue":"2","key":"159_CR26","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10107-006-0043-y","volume":"112","author":"E Uchoa","year":"2008","unstructured":"Uchoa E, Fukasawa R, Lysgaard J, Pessoa A, de Arag\u00e3o MP, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math Programm 112(2):443\u2013472. doi:\n                        10.1007\/s10107-006-0043-y","journal-title":"Math Programm"},{"key":"159_CR27","unstructured":"Zhou F, Molnar M, Cousin B (2010) Light-hierarchy: the optimal structure for multicast routing in wdm mesh networks. In: ISCC, pp 611\u2013616"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0159-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0159-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0159-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,3]],"date-time":"2018-09-03T12:57:28Z","timestamp":1535979448000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0159-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["159"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0159-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,8,9]]}}}