{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:08Z","timestamp":1740122408531,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T00:00:00Z","timestamp":1633564800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T00:00:00Z","timestamp":1633564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2018-05066"],"award-info":[{"award-number":["RGPIN-2018-05066"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10878-021-00813-2","type":"journal-article","created":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T12:24:14Z","timestamp":1633609454000},"page":"51-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Network construction\/restoration problems: cycles and complexity"],"prefix":"10.1007","volume":"44","author":[{"given":"Tianyu","family":"Wang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6168-4424","authenticated-orcid":false,"given":"Igor","family":"Averbakh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,7]]},"reference":[{"key":"813_CR1","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1016\/j.ejor.2019.03.024","volume":"277","author":"M Ajam","year":"2019","unstructured":"Ajam M, Akbari V, Salman FS (2019) Minimizing latency in post-disaster road clearance operations. Eur J Oper Res 277:1098\u20131112","journal-title":"Eur J Oper Res"},{"issue":"2","key":"813_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1287\/opre.1120.1134","volume":"61","author":"S Alpern","year":"2013","unstructured":"Alpern S, Lidbetter T (2013) Mining coal or finding terrorists: the expanding search paradigm. Oper Res 61(2):265\u2013279","journal-title":"Oper Res"},{"key":"813_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg S, Proskurovski A (1989) Linear time algorithms for NP-hard problems restricted to partial $$k$$-trees. Discrete Appl Math 23:11\u201324","journal-title":"Discrete Appl Math"},{"issue":"8","key":"813_CR4","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1080\/0740817X.2011.636792","volume":"44","author":"I Averbakh","year":"2012","unstructured":"Averbakh I, Pereira J (2012) The flowtime network construction problem. IIE Trans 44(8):681\u2013694","journal-title":"IIE Trans"},{"key":"813_CR5","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.ejor.2015.02.014","volume":"244","author":"I Averbakh","year":"2015","unstructured":"Averbakh I, Pereira J (2015) Network construction problems with due dates. Eur J Oper Res 244:715\u2013729","journal-title":"Eur J Oper Res"},{"issue":"3","key":"813_CR6","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1287\/ijoc.2017.0796","volume":"30","author":"I Averbakh","year":"2018","unstructured":"Averbakh I, Pereira J (2018) Lateness minimization in pairwise connectivity restoration problems. INFORMS J Comput 30(3):522\u2013538","journal-title":"INFORMS J Comput"},{"key":"813_CR7","doi-asserted-by":"publisher","first-page":"105190","DOI":"10.1016\/j.cor.2020.105190","volume":"128","author":"I Averbakh","year":"2021","unstructured":"Averbakh I, Pereira J (2021) Tree optimization based heuristics and metaheuristics in network construction problems. Comput Oper Res 128:105190. https:\/\/doi.org\/10.1016\/j.cor.2020.105190","journal-title":"Comput Oper Res"},{"key":"813_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1023\/A:1014509708610","volume":"106","author":"A Balakrishnan","year":"2001","unstructured":"Balakrishnan A, Magnanti TL, Sokol JS, Wang Y (2001) Telecommunication link restoration planning with multiple facility types. Ann Oper Res 106:127\u2013154","journal-title":"Ann Oper Res"},{"issue":"4","key":"813_CR9","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1287\/opre.50.4.617.2853","volume":"50","author":"A Balakrishnan","year":"2002","unstructured":"Balakrishnan A, Magnanti TL, Sokol JS, Wang Y (2002) Spare-capacity assignment for line restoration using a single facility type. Oper Res 50(4):617\u2013635","journal-title":"Oper Res"},{"key":"813_CR10","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1016\/j.ejor.2014.04.018","volume":"238","author":"M Baxter","year":"2014","unstructured":"Baxter M, Elgindy T, Ernst A, Kalinowski T, Savelsbergh MWP (2014) Incremental network design with shortest paths. Eur J Oper Res 238:675\u2013684","journal-title":"Eur J Oper Res"},{"issue":"3\u20134","key":"813_CR11","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s13675-016-0063-1","volume":"4","author":"N Berktas","year":"2016","unstructured":"Berktas N, Kara BY, Karasan OE (2016) Solution methodologies for debris removal in disaster response. EURO J Comput Optim 4(3\u20134):403\u2013445","journal-title":"EURO J Comput Optim"},{"issue":"1","key":"813_CR12","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/opre.2014.1342","volume":"63","author":"M Celic","year":"2015","unstructured":"Celic M, Ergun O, Keskinocak P (2015) The post-disaster debris clearance problem under incomplete information. Oper Res 63(1):65\u201385","journal-title":"Oper Res"},{"key":"813_CR13","first-page":"47","volume":"21","author":"M Celik","year":"2016","unstructured":"Celik M (2016) Network restoration and recovery in humanitarian operations: framework, literature review, and research directions. Surv Oper Res Manag Sci 21:47\u201361","journal-title":"Surv Oper Res Manag Sci"},{"issue":"2","key":"813_CR14","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1287\/ijoc.1030.0052","volume":"16","author":"WE de Paepe","year":"2004","unstructured":"de Paepe WE, Lenstra JK, Sgall J, Sitters R, Stougie L (2004) Computer-aided complexity classification of dial-a-ride problems. INFORMS J Comput 16(2):120\u2013132","journal-title":"INFORMS J Comput"},{"key":"813_CR15","unstructured":"Engel K, Kalinowski T, Savelsbergh MWP (2013) Incremental network design with minimum spanning trees. arXiv:1306.1926v1"},{"issue":"4","key":"813_CR16","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U Feige","year":"2004","unstructured":"Feige U, Lovasz L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219\u2013234","journal-title":"Algorithmica"},{"issue":"6","key":"813_CR17","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M Fischetti","year":"1993","unstructured":"Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper Res 41(6):1055\u20131064","journal-title":"Oper Res"},{"issue":"1","key":"813_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"GN Frederickson","year":"1998","unstructured":"Frederickson GN, Johnson DB (1998) Finding $$k$$-th paths and $$p$$-centers by generating and searching good data structures. J Algorithms 4(1):61\u201380","journal-title":"J Algorithms"},{"issue":"1","key":"813_CR19","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.ejor.2008.03.001","volume":"196","author":"L Fu","year":"2009","unstructured":"Fu L, Trudel M, Kim V (2009) Optimizing winter road maintenance operations under real-time information. Eur J Oper Res 196(1):332\u2013341","journal-title":"Eur J Oper Res"},{"key":"813_CR20","volume-title":"Computers and intractability","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability. Freeman, New York"},{"issue":"4","key":"813_CR21","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0097539791218664","volume":"24","author":"DW Gillies","year":"1995","unstructured":"Gillies DW, Liu J (1995) Scheduling tasks with AND\/OR precedence constraints. SIAM J Comput 24(4):797\u2013810","journal-title":"SIAM J Comput"},{"key":"813_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0166-218X(92)00122-3","volume":"48","author":"D Granot","year":"1994","unstructured":"Granot D, Skorin-Kapov D (1994) On some optimization problems on $$k$$-trees and partial $$k$$-trees. Discrete Appl Math 48:129\u2013145","journal-title":"Discrete Appl Math"},{"key":"813_CR23","doi-asserted-by":"crossref","unstructured":"Guha S, Moss A, Naor JS, Schieber B (1999) Efficient recovery from power outage. In: Vitter J, Larmore L, Leighton F (eds) Proceedings of the thirty-first annual ACM symposium on theory of computing (STOC), Atlanta, pp 574\u2013582","DOI":"10.1145\/301250.301406"},{"key":"813_CR24","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2002","unstructured":"Gutin G, Punnen A (2002) The traveling salesman problem and its variations. Kluwer, Dordrecht"},{"key":"813_CR25","unstructured":"Happach F, Hellerstein L, Lidbetter T (2020) A general framework for approximating min sum ordering problems. arXiv:2004.05954"},{"key":"813_CR26","unstructured":"Hermans B, Leus R, Matuschke J (2019) Exact and approximation algorithms for the expanding search problem. arXiv:1911.08959v1, November 20, 2019. To appear in INFORMS J Comput"},{"key":"813_CR27","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.trb.2013.05.010","volume":"55","author":"ZH Hu","year":"2013","unstructured":"Hu ZH, Sheu JB (2013) Post-disaster debris reverse logistics management under psychological cost minimization. Transport Res Part B 55:118\u2013141","journal-title":"Transport Res Part B"},{"key":"813_CR28","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.proeng.2015.06.069","volume":"107","author":"A Lorka","year":"2015","unstructured":"Lorka A, Celik M, Ergun O, Keskinocak P (2015) A decision-support tool for post-disaster debris operations. Procedia Eng 107:154\u2013167","journal-title":"Procedia Eng"},{"issue":"3","key":"813_CR29","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s11067-009-9123-x","volume":"10","author":"TC Matisziw","year":"2010","unstructured":"Matisziw TC, Murray AT, Grubesic TH (2010) Strategic network restoration. Netw Spacial Econ 10(3):345\u2013361","journal-title":"Netw Spacial Econ"},{"issue":"2","key":"813_CR30","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/S009753970037727X","volume":"33","author":"RH Mohring","year":"2004","unstructured":"Mohring RH, Skutella M, Stork F (2004) Scheduling with AND\/OR precedence constraints. SIAM J Comput 33(2):393\u2013415","journal-title":"SIAM J Comput"},{"issue":"4","key":"813_CR31","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1002\/net.21547","volume":"63","author":"SG Nurre","year":"2014","unstructured":"Nurre SG, Sharkey TC (2014) Integrated network design and scheduling problems with parallel identical machines: complexity results and dispatching rules. Networks 63(4):306\u2013326","journal-title":"Networks"},{"key":"813_CR32","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1016\/j.ejor.2012.07.010","volume":"223","author":"SC Nurre","year":"2012","unstructured":"Nurre SC, Cavdaroglu B, Mitchell JE, Sharkey TC, Wallace WA (2012) Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem. Eur J Oper Res 223:794\u2013806","journal-title":"Eur J Oper Res"},{"issue":"7","key":"813_CR33","doi-asserted-by":"publisher","first-page":"1432","DOI":"10.1016\/j.cor.2011.08.014","volume":"39","author":"MA Salazar-Aguilar","year":"2012","unstructured":"Salazar-Aguilar MA, Langevin A, Laporte G (2012) Synchronized arc routing for snow plowing operations. Comput Oper Res 39(7):1432\u20131440","journal-title":"Comput Oper Res"},{"issue":"1","key":"813_CR34","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.ejor.2014.12.051","volume":"244","author":"TC Sharkey","year":"2015","unstructured":"Sharkey TC, Cavdaroglu B, Nguyen H, Holman J, Mitchell JE, Wallace WA (2015) Independent network restoration: on the value of information-sharing. Eur J Oper Res 244(1):309\u2013321","journal-title":"Eur J Oper Res"},{"key":"813_CR35","doi-asserted-by":"crossref","unstructured":"Sitters R (2002) The minimum latency problem is NP-hard for weighted trees. In: International conference on integer programming and combinatorial optimization. Springer, Berlin, pp 230\u2013239","DOI":"10.1007\/3-540-47867-1_17"},{"issue":"3","key":"813_CR36","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K Takamizawa","year":"1982","unstructured":"Takamizawa K, Mishizeki T, Saito N (1982) Linear-time computability of combinatorial problems on series-parallel graphs. J Assoc Comput Mach 29(3):623\u2013641","journal-title":"J Assoc Comput Mach"},{"key":"813_CR37","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/net.3230220305","volume":"22","author":"JN Tsitsiklis","year":"1992","unstructured":"Tsitsiklis JN (1992) Special cases of traveling salesman and repairman problems with time windows. Networks 22:263\u2013244","journal-title":"Networks"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00813-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00813-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-00813-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:26:49Z","timestamp":1659079609000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00813-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["813"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00813-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,10,7]]},"assertion":[{"value":"24 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}