{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:35Z","timestamp":1740122375162,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425297\/2016-0","309315\/2019-0"],"award-info":[{"award-number":["425297\/2016-0","309315\/2019-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425297\/2016-0","304576\/2017-4"],"award-info":[{"award-number":["425297\/2016-0","304576\/2017-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["PRONEM 0112.00061.01.00-16"],"award-info":[{"award-number":["PRONEM 0112.00061.01.00-16"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DEMOGRAPH","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}]},{"name":"ESIGMA","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]},{"name":"ELIT","award":["ANR-20-CE48-0008-01"],"award-info":[{"award-number":["ANR-20-CE48-0008-01"]}]},{"name":"CAPES-PRINT","award":["88887.468331\/2019-00"],"award-info":[{"award-number":["88887.468331\/2019-00"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10878-021-00740-2","type":"journal-article","created":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T08:05:46Z","timestamp":1618819546000},"page":"125-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A unifying model for locally constrained spanning tree problems"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5728-3484","authenticated-orcid":false,"given":"Luiz","family":"Viana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2962-2033","authenticated-orcid":false,"given":"Manoel","family":"Camp\u00ealo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8981-9287","authenticated-orcid":false,"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8917-0564","authenticated-orcid":false,"given":"Ana","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"issue":"1","key":"740_CR1","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.cor.2009.03.006","volume":"37","author":"I Akg\u00fcn","year":"2010","unstructured":"Akg\u00fcn I, Tansel B (2010) Min-degree constrained minimum spanning tree problem: new formulation via Miller\u2013Tucker\u2013Zemlin constraints. Comput Oper Res 37(1):72\u201382","journal-title":"Comput Oper Res"},{"key":"740_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.endm.2010.05.002","volume":"36","author":"AM Almeida","year":"2010","unstructured":"Almeida AM, Martins P, Souza MC (2010) md-MST is NP-hard for $$d\\ge 3$$. Electron Notes Discrete Math 36:9\u201315","journal-title":"Electron Notes Discrete Math"},{"issue":"3","key":"740_CR3","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1111\/j.1475-3995.2011.00830.x","volume":"19","author":"AM Almeida","year":"2012","unstructured":"Almeida AM, Martins P, de Souza MC (2012) Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations. Int Trans Oper Res 19(3):323\u2013352","journal-title":"Int Trans Oper Res"},{"issue":"2","key":"740_CR4","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J Algorithms 12(2):308\u2013340. https:\/\/doi.org\/10.1016\/0196-6774(91)90006-K","journal-title":"J Algorithms"},{"key":"740_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, Cambridge"},{"issue":"2","key":"740_CR6","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00453-015-0076-9","volume":"77","author":"R Aschner","year":"2017","unstructured":"Aschner R, Katz MJ (2017) Bounded-angle spanning tree: modeling networks with angular constraints. Algorithmica 77(2):349\u2013373","journal-title":"Algorithmica"},{"issue":"3","key":"740_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1002\/net.21923","volume":"75","author":"J Baste","year":"2020","unstructured":"Baste J, G\u00f6z\u00fcpek D, Paul C, Sau I, Shalom M, Thilikos DM (2020) Parameterized complexity of finding a spanning tree with minimum reload cost diameter. Networks 75(3):259\u2013277. https:\/\/doi.org\/10.1002\/net.21923","journal-title":"Networks"},{"issue":"3","key":"740_CR8","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s10589-015-9788-7","volume":"63","author":"LH Bicalho","year":"2016","unstructured":"Bicalho LH, da Cunha AS, Lucena A (2016) Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem. Comput Optim Appl 63(3):755\u2013792","journal-title":"Comput Optim Appl"},{"key":"740_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender HL, Jansen K (1993) On the complexity of scheduling incompatible jobs with unit-times. In: Borzyszkowski A, Soko\u0142owski S (eds) MFCS\u2014international symposium on mathematical foundations of computer science. Springer, Berlin, pp 191\u2013300","DOI":"10.1007\/3-540-57182-5_21"},{"issue":"5","key":"740_CR10","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0377-2217(80)90164-2","volume":"5","author":"PM Camerini","year":"1980","unstructured":"Camerini PM, Galbiati G, Maffioli F (1980) Complexity of spanning tree problems: part I. Eur J Oper Res 5(5):346\u2013352","journal-title":"Eur J Oper Res"},{"issue":"1","key":"740_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0166-218X(83)90014-8","volume":"5","author":"PM Camerini","year":"1983","unstructured":"Camerini PM, Galbiati G, Maffioli F (1983) On the complexity of finding multi-constrained spanning trees. Discrete Appl Math 5(1):39\u201350","journal-title":"Discrete Appl Math"},{"key":"740_CR12","first-page":"1","volume":"2018","author":"F Carrabs","year":"2018","unstructured":"Carrabs F, Cerulli R, Pentangelo R, Raiconi A (2018) Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach. Ann Oper Res 2018:1\u201314","journal-title":"Ann Oper Res"},{"issue":"2","key":"740_CR13","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1002\/net.21883","volume":"74","author":"F Carrabs","year":"2019","unstructured":"Carrabs F, Cerrone C, Pentangelo R (2019) A multiethnic genetic approach for the minimum conflict weighted spanning tree problem. Networks 74(2):134\u2013147","journal-title":"Networks"},{"key":"740_CR14","doi-asserted-by":"crossref","unstructured":"Cook SA (1971) The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing, pp 151\u2013158","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"740_CR15","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle B (1990) The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf Comput 85(1):12\u201375. https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inf Comput"},{"key":"740_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin"},{"key":"740_CR17","doi-asserted-by":"publisher","first-page":"104775","DOI":"10.1016\/j.cor.2019.104775","volume":"112","author":"AS da Cunha","year":"2019","unstructured":"da Cunha AS, Lucena A (2019) Modeling and solving the angular constrained minimum spanning tree problem. Comput Oper Res 112:104775","journal-title":"Comput Oper Res"},{"key":"740_CR18","first-page":"191","volume":"8","author":"A Darmann","year":"2009","unstructured":"Darmann A, Pferschy U, Schauer J (2009) Minimum spanning trees with conflict graphs. Optimization 8:191\u2013205","journal-title":"Optimization"},{"issue":"16","key":"740_CR19","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann A, Pferschy U, Schauer J, Woeginger GJ (2011) Paths, trees and matchings under disjunctive constraints. Discrete Appl Math 159(16):1726\u20131735","journal-title":"Discrete Appl Math"},{"key":"740_CR20","unstructured":"Deo N, Hakimi SL(1968) The shortest generalized Hamiltonian tree. In: Proceedings of the 6th annual Allerton conference, vol 17(3), pp 409\u2013423"},{"key":"740_CR21","doi-asserted-by":"crossref","unstructured":"Deo N, Kumar N (1997) Computation of constrained spanning trees: a unified approach. In: Network optimization, vol 450. Lecture notes in economics and mathematical systems. Springer, Berlin, pp 196\u2013220","DOI":"10.1007\/978-3-642-59179-2_10"},{"key":"740_CR22","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.cor.2017.03.001","volume":"84","author":"FCS Dias","year":"2017","unstructured":"Dias FCS, Camp\u00ealo M, Souza C, Andrade R (2017) Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations. Comput Oper Res 84:46\u201361","journal-title":"Comput Oper Res"},{"key":"740_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume":"4","author":"J Edmonds","year":"1979","unstructured":"Edmonds J (1979) Matroid intersection. Ann Discrete Math 4:39\u201349","journal-title":"Ann Discrete Math"},{"issue":"2","key":"740_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.disopt.2010.11.001","volume":"8","author":"L Epstein","year":"2011","unstructured":"Epstein L, Favrholdt LM, Levin A (2011) Online variable-sized bin packing with conflicts. Discrete Optim 8(2):333\u2013343","journal-title":"Discrete Optim"},{"key":"740_CR25","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. Freeman, San Francisco"},{"key":"740_CR26","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00186-019-00664-y","volume":"89","author":"F Gurski","year":"2019","unstructured":"Gurski F, Rehs C (2019) Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width. Math Methods Oper Res 89:411\u2013432","journal-title":"Math Methods Oper Res"},{"issue":"2","key":"740_CR27","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(94)00183-Y","volume":"53","author":"R Hassin","year":"1995","unstructured":"Hassin R, Tamir A (1995) On the minimum diameter spanning tree problem. Inf Process Lett 53(2):109\u2013111","journal-title":"Inf Process Lett"},{"issue":"5","key":"740_CR28","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1137\/0220060","volume":"20","author":"JM Ho","year":"1991","unstructured":"Ho JM, Lee D, Chang CH, Wong C (1991) Minimum diameter spanning trees and related problems. SIAM J Comput 20(5):987\u2013997","journal-title":"SIAM J Comput"},{"issue":"2","key":"740_CR29","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of $$k$$-SAT. J Comput Syst Sci 62(2):367\u2013375. https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"740_CR30","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530. https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J Comput Syst Sci"},{"key":"740_CR31","doi-asserted-by":"crossref","unstructured":"Kant\u00e9 MM, Laforest C, Mom\u00e8ge B (2013) Trees in graphs with conflict edges or forbidden transitions. In: Proceedings of the of the 10th international conference on theory and applications of models of computation (TAMC), LNCS, vol 7876, pp 343\u2013354","DOI":"10.1007\/978-3-642-38236-9_31"},{"issue":"2","key":"740_CR32","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00453-004-1121-2","volume":"41","author":"J K\u00f6nemann","year":"2005","unstructured":"K\u00f6nemann J, Levin A, Sinha A (2005) Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica 41(2):117\u2013129","journal-title":"Algorithmica"},{"issue":"6","key":"740_CR33","doi-asserted-by":"publisher","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 Heurist 7(6):587\u2013611","journal-title":"J Heurist"},{"key":"740_CR34","volume-title":"Combinatorial optimization: networks and matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler EL (1976) Combinatorial optimization: networks and matroids. Courier Corporation, New York"},{"key":"740_CR35","unstructured":"Lu HI, Ravi R (1992) The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Proceedings of the annual Allerton conference on communication control and computing, vol 30, pp 533\u2013533"},{"issue":"2","key":"740_CR36","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.ipl.2014.07.013","volume":"115","author":"SMS Mapa","year":"2015","unstructured":"Mapa SMS, Urrutia S (2015) On the maximum acyclic subgraph problem under disjunctive constraints. Inf Process Lett 115(2):119\u2013124","journal-title":"Inf Process Lett"},{"key":"740_CR37","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2011.08.008","volume":"164","author":"LC Martinez","year":"2014","unstructured":"Martinez LC, da Cunha AS (2014) The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm. Discrete Appl Math 164:210\u2013224","journal-title":"Discrete Appl Math"},{"key":"740_CR38","volume-title":"Matroid theory","author":"JG Oxley","year":"1992","unstructured":"Oxley JG (1992) Matroid theory. Oxford University Press, Oxford"},{"issue":"2","key":"740_CR39","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou CH, Vazirani UV (1984) On two geometric problems related to the travelling salesman problem. J Algorithms 5(2):231\u2013246","journal-title":"J Algorithms"},{"key":"740_CR40","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","volume":"26","author":"U Pferschy","year":"2013","unstructured":"Pferschy U, Schauer J (2013) The maximum flow problem with disjunctive constraints. J Combin Optim 26:109\u2013119","journal-title":"J Combin Optim"},{"issue":"2","key":"740_CR41","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02570700","volume":"14","author":"G Robins","year":"1995","unstructured":"Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discrete Comput Geom 14(2):151\u2013165","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"740_CR42","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s11590-014-0750-x","volume":"9","author":"P Samer","year":"2015","unstructured":"Samer P, Urrutia S (2015) A branch and cut algorithm for minimum spanning trees under conflict constraints. Optim Lett 9(1):41\u201355","journal-title":"Optim Lett"},{"issue":"1","key":"740_CR43","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2629366","volume":"62","author":"M Singh","year":"2015","unstructured":"Singh M, Lau LC (2015) Approximating minimum bounded degree spanning trees to within one of optimal. J ACM 62(1):1:1\u20131:19","journal-title":"J ACM"},{"key":"740_CR44","unstructured":"Viana LA (2016) \u00c1rvore geradora com depend\u00eancias m\u00ednima. Master\u2019s thesis, Federal University of Cear\u00e1 (2016). http:\/\/mdcc.ufc.br\/teses\/doc_download\/307-234-luiz-alberto-do-carmo-viana"},{"issue":"2","key":"740_CR45","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1111\/itor.12690","volume":"27","author":"LA Viana","year":"2020","unstructured":"Viana LA, Camp\u00ealo M (2020) Two dependency constrained spanning tree problems. Int Trans Oper Res 27(2):867\u2013898. https:\/\/doi.org\/10.1111\/itor.12690","journal-title":"Int Trans Oper Res"},{"key":"740_CR46","volume-title":"Introduction to graph theory","author":"DB West","year":"1996","unstructured":"West DB (1996) Introduction to graph theory. Prentice Hall, Upper Saddle River"},{"issue":"2","key":"740_CR47","doi-asserted-by":"publisher","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. Discrete Optim 8(2):191\u2013205","journal-title":"Discrete Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00740-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00740-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00740-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T05:10:23Z","timestamp":1626066623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00740-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["740"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00740-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"8 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}