{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:15:41Z","timestamp":1761621341776,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,10,11]],"date-time":"2017-10-11T00:00:00Z","timestamp":1507680000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10878-017-0184-3","type":"journal-article","created":{"date-parts":[[2017,10,11]],"date-time":"2017-10-11T09:06:20Z","timestamp":1507712780000},"page":"436-453","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A characterization of linearizable instances of the quadratic minimum spanning tree problem"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4616-2932","authenticated-orcid":false,"given":"Ante","family":"\u0106usti\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,11]]},"reference":[{"key":"184_CR1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.disopt.2014.07.001","volume":"14","author":"W Adams","year":"2014","unstructured":"Adams W, Waddell L (2014) Linear programming insights into solvable cases of the quadratic assignment problem. Discret Optim 14:46\u201360","journal-title":"Discret Optim"},{"key":"184_CR2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/1520-6750(199204)39:3<399::AID-NAV3220390309>3.0.CO;2-0","volume":"39","author":"A Assad","year":"1992","unstructured":"Assad A, Xu W (1992) The quadratic minimum spanning tree problem. Naval Res Logist 39:399\u2013417","journal-title":"Naval Res Logist"},{"key":"184_CR3","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1080\/02331939008843626","volume":"21","author":"I Bookhold","year":"1990","unstructured":"Bookhold I (1990) A contribution to quadratic assignment problems. Optimization 21:933\u2013943","journal-title":"Optimization"},{"key":"184_CR4","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.dam.2014.05.031","volume":"177","author":"C Buchheim","year":"2014","unstructured":"Buchheim C, Klein L (2014) Combinatorial optimization with one quadratic term: spanning trees and forests. Discret Appl Math 177:34\u201352","journal-title":"Discret Appl Math"},{"key":"184_CR5","doi-asserted-by":"crossref","first-page":"1269","DOI":"10.1007\/s10878-014-9821-2","volume":"31","author":"E \u00c7ela","year":"2016","unstructured":"\u00c7ela E, De\u012dneko VG, Woeginger GJ (2016) Linearizable special cases of the QAP. J Comb Optim 31:1269\u20131279","journal-title":"J Comb Optim"},{"key":"184_CR6","first-page":"11597","volume":"218","author":"R Cordone","year":"2012","unstructured":"Cordone R, Passeri G (2012) Solving the quadratic minimum spanning tree problem. Appl Math Comput 218:11597\u201311612","journal-title":"Appl Math Comput"},{"key":"184_CR7","unstructured":"\u0106usti\u0107 A (2014) Efficiently solvable special cases of multidimensional assignment problems. Ph.D. thesis, TU Graz"},{"key":"184_CR8","doi-asserted-by":"publisher","unstructured":"\u0106usti\u0107 A, Sokol V, Punnen AP, Bhattacharya B (2017) The bilinear assignment problem: complexity and polynomially solvable special cases. Math Program. doi:\n                        10.1007\/s10107-017-1111-1","DOI":"10.1007\/s10107-017-1111-1"},{"key":"184_CR9","doi-asserted-by":"publisher","unstructured":"\u0106usti\u0107 A, Zhang R, Punnen AP (2016) The quadratic minimum spanning tree problem and its variations. Discrete Optim. doi:\n                        10.1016\/j.disopt.2017.09.003","DOI":"10.1016\/j.disopt.2017.09.003"},{"key":"184_CR10","doi-asserted-by":"crossref","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann A, Pferschy U, Schauer S, Woeginger GJ (2011) Paths, trees and matchings under disjunctive constraints. Discret Appl Math 159:1726\u20131735","journal-title":"Discret Appl Math"},{"key":"184_CR11","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1016\/j.orl.2013.09.011","volume":"41","author":"A Fischer","year":"2013","unstructured":"Fischer A, Fischer F (2013) Complete description for the spanning tree problem with one linearised quadratic term. Oper Res Lett 41:701\u2013705","journal-title":"Oper Res Lett"},{"key":"184_CR12","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.engappai.2015.08.012","volume":"46","author":"ZH Fu","year":"2015","unstructured":"Fu ZH, Hao JK (2015) A three-phase search approach for the quadratic minimum spanning tree problem. Eng Appl Artif Intell 46:113\u2013130","journal-title":"Eng Appl Artif Intell"},{"key":"184_CR13","first-page":"773","volume":"164","author":"J Gao","year":"2005","unstructured":"Gao J, Lu M (2005) Fuzzy quadratic minimum spanning tree problem. Appl Math Comput 164:773\u2013788","journal-title":"Appl Math Comput"},{"key":"184_CR14","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s10107-009-0287-4","volume":"126","author":"V Goyal","year":"2011","unstructured":"Goyal V, Genc-Kaya L, Ravi R (2011) An FPTAS for minimizing the product of two non-negative linear cost functions. Math Program 126:401\u2013405","journal-title":"Math Program"},{"key":"184_CR15","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R (1973) Efficient algorithm for graph manipulation. Commun ACM 16:372\u2013378","journal-title":"Commun ACM"},{"key":"184_CR16","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1287\/moor.1110.0509","volume":"36","author":"SN Kabadi","year":"2011","unstructured":"Kabadi SN, Punnen AP (2011) An \n                        $$O(n^4)$$\n                        \n                            \n                                \n                                    O\n                                    (\n                                    \n                                        n\n                                        4\n                                    \n                                    )\n                                \n                            \n                        \n                     algorithm for the QAP linearization problem. Math Oper Res 36:754\u2013761","journal-title":"Math Oper Res"},{"key":"184_CR17","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s10107-006-0047-7","volume":"110","author":"W Kern","year":"2007","unstructured":"Kern W, Woeginger GJ (2007) Quadratic programming and combinatorial minimum weight product problems. Math Program 110:641\u2013649","journal-title":"Math Program"},{"key":"184_CR18","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1080\/0740817X.2013.768785","volume":"46","author":"M Lozano","year":"2014","unstructured":"Lozano M, Glover F, Garcia-Martinez C, Rodriguez JF, Marti R (2014) Tabu search with strategic oscillation for the quadratic minimum spanning tree. IIE Trans 46:414\u2013428","journal-title":"IIE Trans"},{"key":"184_CR19","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/j.endm.2013.05.135","volume":"41","author":"SMDM Maia","year":"2013","unstructured":"Maia SMDM, Goldbarg EFG, Goldbarg MC (2013) On the biobjective adjacent only quadratic spanning tree problem. Electron Notes Discret Math 41:535\u2013542","journal-title":"Electron Notes Discret Math"},{"key":"184_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1504\/IJICA.2014.066493","volume":"6","author":"SMDM Maia","year":"2014","unstructured":"Maia SMDM, Goldbarg EFG, Goldbarg MC (2014) Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree. Int J Innovative Comput Appl 6:63\u201372","journal-title":"Int J Innovative Comput Appl"},{"key":"184_CR21","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s10107-011-0511-x","volume":"141","author":"S Mittal","year":"2013","unstructured":"Mittal S, Schulz AS (2013) An FPTAS for optimizing a class of low-rank functions over a polytope. Math Program 141:103\u2013120","journal-title":"Math Program"},{"key":"184_CR22","doi-asserted-by":"crossref","first-page":"1762","DOI":"10.1016\/j.cor.2010.01.004","volume":"37","author":"T \u00d6ncan","year":"2010","unstructured":"\u00d6ncan T, Punnen AP (2010) The quadratic minimum spanning tree probelm: a lower bounding procedure and an efficient search algorithm. Comput Oper Res 37:1762\u20131773","journal-title":"Comput Oper Res"},{"key":"184_CR23","first-page":"257","volume":"29","author":"G Palubeckis","year":"2010","unstructured":"Palubeckis G, Rubliauskas D, Targamadz\u0117 A (2010) Metaheuristic approaches for the quadratic minimum spanning tree problem. Inf Technol Control 29:257\u2013268","journal-title":"Inf Technol Control"},{"key":"184_CR24","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.endm.2013.05.097","volume":"41","author":"DL Pereira","year":"2013","unstructured":"Pereira DL, Gendreau M, da Cunha AS (2013) Stronger lower bounds for the quadratic minimum spanning tree problem with adjacency costs. Electron Notes Discret Math 41:229\u2013236","journal-title":"Electron Notes Discret Math"},{"key":"184_CR25","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1002\/net.21580","volume":"65","author":"DL Pereira","year":"2015","unstructured":"Pereira DL, Gendreau M, da Cunha AS (2015) Branch-and-cut and Branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem. Networks 65:367\u2013379","journal-title":"Networks"},{"key":"184_CR26","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.cor.2015.04.020","volume":"63","author":"DL Pereira","year":"2015","unstructured":"Pereira DL, Gendreau M, da Cunha AS (2015) Lower bounds and exact algorithms for the quadratic minimum spanning tree problem. Comput Oper Res 63:149\u2013160","journal-title":"Comput Oper Res"},{"key":"184_CR27","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","volume":"10","author":"AP Punnen","year":"2013","unstructured":"Punnen AP, Kabadi SN (2013) A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discret Optim 10:200\u2013209","journal-title":"Discret Optim"},{"key":"184_CR28","first-page":"205","volume":"7","author":"AP Punnen","year":"2001","unstructured":"Punnen AP (2001) Combinatorial optimization with multiplicative objective function. Int J Oper Quant Manag 7:205\u2013209","journal-title":"Int J Oper Quant Manag"},{"key":"184_CR29","unstructured":"Punnen AP, Woods B (2017) A characterizations of linearizable instances of the quadratic travelling salesman problem. \n                        arXiv:1708.07217v2\n                        \n                     [cs.DM]"},{"key":"184_CR30","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.cor.2015.06.005","volume":"64","author":"B Rostami","year":"2015","unstructured":"Rostami B, Malucelli F (2015) Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation. Comput Oper Res 64:178\u2013188","journal-title":"Comput Oper Res"},{"key":"184_CR31","doi-asserted-by":"crossref","first-page":"3182","DOI":"10.1016\/j.ins.2010.05.001","volume":"180","author":"S Sundar","year":"2010","unstructured":"Sundar S, Singh A (2010) A swarm intelligence approach to the quadratic minimum spanning tree problem. Inf Sci 180:3182\u20133191","journal-title":"Inf Sci"},{"key":"184_CR32","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.disopt.2010.08.001","volume":"8","author":"R Zhang","year":"2011","unstructured":"Zhang R, Kabadi SN, Punnen AP (2011) The minimum spanning tree problem with conflict constraints and its variations. Discret Optim 8:191\u2013205","journal-title":"Discret Optim"},{"key":"184_CR33","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0305-0548(97)00039-7","volume":"25","author":"G Zhou","year":"1998","unstructured":"Zhou G, Gen M (1998) An effective genetic algorithm approach to the quadratic minimum spanning tree problem. Comput Oper Res 25:229\u2013237","journal-title":"Comput Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0184-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0184-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0184-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T07:39:48Z","timestamp":1518161988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0184-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,11]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["184"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0184-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,10,11]]}}}