{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:04:21Z","timestamp":1756310661804,"version":"3.37.3"},"reference-count":87,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,11,21]],"date-time":"2017-11-21T00:00:00Z","timestamp":1511222400000},"content-version":"tdm","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,11]]},"DOI":"10.1007\/s10878-017-0213-2","type":"journal-article","created":{"date-parts":[[2017,11,21]],"date-time":"2017-11-21T21:01:24Z","timestamp":1511298084000},"page":"1262-1298","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A quadratic time exact algorithm for continuous connected 2-facility location problem in trees"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4353-5385","authenticated-orcid":false,"given":"Wei","family":"Ding","sequence":"first","affiliation":[]},{"given":"Ke","family":"Qiu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,21]]},"reference":[{"issue":"3","key":"213_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501\u2013555","journal-title":"J ACM"},{"issue":"2","key":"213_CR2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/net.10062","volume":"41","author":"I Averbakh","year":"2003","unstructured":"Averbakh I, Berman O (2003) An improved algorithm for the minmax regret median problem on a tree. Networks 41(2):97\u2013103","journal-title":"Networks"},{"issue":"2","key":"213_CR3","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/S0377-2217(99)00257-X","volume":"123","author":"I Averbakh","year":"2000","unstructured":"Averbakh I, Berman O (2000) Algorithms for the robust 1-center problem on a tree. Eur J Oper Res 123(2):292\u2013302","journal-title":"Eur J Oper Res"},{"issue":"4","key":"213_CR4","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0966-8349(98)00033-3","volume":"5","author":"I Averbakh","year":"1997","unstructured":"Averbakh I, Berman O (1997) Minimax regret $$p$$ p -center location on a network with demand uncertainty. Locat Sci 5(4):247\u2013254","journal-title":"Locat Sci"},{"issue":"2","key":"213_CR5","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/ijoc.12.2.104.11897","volume":"12","author":"I Averbakh","year":"2000","unstructured":"Averbakh I, Berman O (2000) Minmax regret median location on a network under uncertainty. INFORMS J Comput 12(2):104\u2013110","journal-title":"INFORMS J Comput"},{"key":"213_CR6","unstructured":"Banik A, Bhattacharya B, Das S, Kameda T, Song Z (2016) The $$p$$ p -center problem in tree networks revisited. In: Proceedings of 15th SWAT, LIPICS, pp 6:1\u20136:15"},{"issue":"4","key":"213_CR7","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1287\/ijoc.1090.0375","volume":"22","author":"MG Bardossy","year":"2010","unstructured":"Bardossy MG, Raghavan S (2010) Dual-based local search for the connected facility location and related problems. INFORMS J Comput 22(4):584\u2013602","journal-title":"INFORMS J Comput"},{"issue":"3","key":"213_CR8","doi-asserted-by":"crossref","first-page":"1208","DOI":"10.1016\/j.ejor.2005.09.049","volume":"179","author":"RI Becker","year":"2007","unstructured":"Becker RI, Lari I, Scozzari A (2007) Algorithms for central-median paths with bounded length on trees. Eur J Oper Res 179(3):1208\u20131220","journal-title":"Eur J Oper Res"},{"key":"213_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Moshe B, Bhattacharya B, Shi QS (2006) An optimal algorithm for the continuous\/discrete weighted 2-center problem in trees. In: Proceedings of 7th LATIN, LNCS 3887, pp 166\u2013177","DOI":"10.1007\/11682462_19"},{"key":"213_CR10","unstructured":"Benkoczi R (2004) Cardinality constrained facility location problems in trees. Ph.D. Dissertation, School of Computing Science, Simon Fraser University, Canada"},{"key":"213_CR11","unstructured":"Benkoczi R, Bhattacharya B, Chrobak M, Larmore L, Rytter W (2003) Faster algorithms for $$k$$ k -median problems in trees. In: Proceedings of 28th MFCS, LNCS 2747, pp 218\u2013227"},{"issue":"1","key":"213_CR12","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.20258","volume":"53","author":"R Benkoczi","year":"2009","unstructured":"Benkoczi R, Bhattacharya B, Tamir A (2009) Collection depots facility location problems in trees. Networks 53(1):50\u201362","journal-title":"Networks"},{"issue":"1","key":"213_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/net.3230180106","volume":"18","author":"O Berman","year":"1988","unstructured":"Berman O, Simchi-Levi D, Tamir A (1988) The minimax multistop location problem on a tree. Networks 18(1):39\u201349","journal-title":"Networks"},{"issue":"4","key":"213_CR14","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s00453-007-9157-8","volume":"55","author":"B Bhattacharya","year":"2009","unstructured":"Bhattacharya B, Shi QS, Tamir A (2009) Optimal algorithms for the path\/tree-shaped facility location problems in trees. Algorithmica 55(4):601\u2013618","journal-title":"Algorithmica"},{"issue":"1","key":"213_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/s00453-013-9851-7","volume":"70","author":"B Bhattacharya","year":"2014","unstructured":"Bhattacharya B, Kameda T, Song Z (2014) A linear time algorithm for computing minmax regret 1-median on a tree network. Algorithmica 70(1):2\u201321","journal-title":"Algorithmica"},{"key":"213_CR16","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.dam.2014.10.022","volume":"195","author":"B Bhattacharya","year":"2015","unstructured":"Bhattacharya B, Kameda T, Song Z (2015) Minmax regret 1-center algorithms for path\/tree\/unicycle\/cactus networks. Discrete Appl Math 195:18\u201330","journal-title":"Discrete Appl Math"},{"issue":"1","key":"213_CR17","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.orl.2007.02.012","volume":"36","author":"G Brodal","year":"2008","unstructured":"Brodal G, Georgiadis L, Katriel I (2008) An $$O(n \\log n)$$ O ( n log n ) version of the Averbakh\u2013Berman algorithm for the robust median of a tree. Oper Res Lett 36(1):14\u201318","journal-title":"Oper Res Lett"},{"issue":"1\u20133","key":"213_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0166-218X(00)00177-3","volume":"105","author":"RE Burkard","year":"2000","unstructured":"Burkard RE, Cela E, Dollani H (2000) 2-Medians in trees with pos\/neg weights. Discrete Appl Math 105(1\u20133):51\u201371","journal-title":"Discrete Appl Math"},{"issue":"3","key":"213_CR19","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1016\/S0377-2217(02)00211-4","volume":"145","author":"RE Burkard","year":"2003","unstructured":"Burkard RE, Dollani H (2003) Center problems with pos\/neg weights on trees. Eur J Oper Res 145(3):483\u2013495","journal-title":"Eur J Oper Res"},{"issue":"1","key":"213_CR20","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1023\/A:1020711416254","volume":"110","author":"RE Burkard","year":"2002","unstructured":"Burkard RE, Dollani H (2002) A note on the robust 1-center problem on trees. Ann OR 110(1):69\u201382","journal-title":"Ann OR"},{"issue":"2","key":"213_CR21","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1002\/net.1029","volume":"38","author":"RE Burkard","year":"2001","unstructured":"Burkard RE, Dollani H (2001) Robust location problems with pos\/neg weights on a tree. Networks 38(2):102\u2013113","journal-title":"Networks"},{"issue":"4","key":"213_CR22","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1137\/S0895480198340967","volume":"14","author":"RE Burkard","year":"2001","unstructured":"Burkard RE, Dollani H, Lin YX, Rote G (2001) The obnoxious center problem on a tree. SIAM J Discrete Math 14(4):498\u2013509","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"213_CR23","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00186-006-0121-1","volume":"65","author":"RE Burkard","year":"2007","unstructured":"Burkard RE, Fathali J (2007) A polynomial method for the pos\/neg weighted 3-median problem on a tree. Math Methods OR 65(2):229\u2013238","journal-title":"Math Methods OR"},{"issue":"3","key":"213_CR24","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.orl.2006.03.016","volume":"35","author":"RE Burkard","year":"2007","unstructured":"Burkard RE, Fathali J, Kakhki HT (2007) The $$p$$ p -maxian problem on a tree. Oper Res Lett 35(3):331\u2013335","journal-title":"Oper Res Lett"},{"key":"213_CR25","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1016\/j.tcs.2008.11.021","volume":"410","author":"CY Chan","year":"2009","unstructured":"Chan CY, Ku SC, Lu CJ, Wang BF (2009) Efficient algorithms for two generalized 2-median problems and the group median problem on trees. Theor Comput Sci 410:867\u2013876","journal-title":"Theor Comput Sci"},{"issue":"1","key":"213_CR26","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/BF01581045","volume":"22","author":"R Chandrasekaran","year":"1982","unstructured":"Chandrasekaran R, Tamir A (1982) Polynomially bounded algorithms for locating $$p$$ p -centers on a tree. Math Program 22(1):304\u2013315","journal-title":"Math Program"},{"issue":"4","key":"213_CR27","first-page":"370","volume":"1","author":"R Chandrasekaran","year":"1980","unstructured":"Chandrasekaran R, Tamir A (1980) An $$O((n \\log p)^2)$$ O ( ( n log p ) 2 ) algorithm for the continuous $$p$$ p -center problem on a tree. SIAM J Matrix Anal Appl 1(4):370\u2013375","journal-title":"SIAM J Matrix Anal Appl"},{"issue":"2","key":"213_CR28","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1002\/(SICI)1097-0037(199803)31:2<93::AID-NET4>3.0.CO;2-E","volume":"31","author":"B Chen","year":"1998","unstructured":"Chen B, Lin C (1998) Minmax-regret robust 1-median location on a tree. Networks 31(2):93\u2013103","journal-title":"Networks"},{"issue":"2","key":"213_CR29","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1287\/trsc.12.2.107","volume":"12","author":"RL Church","year":"1978","unstructured":"Church RL, Garfinkel RS (1978) Locating an obnoxious facility on a network. Transp Sci 12(2):107\u2013118","journal-title":"Transp Sci"},{"issue":"2","key":"213_CR30","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.orl.2007.05.009","volume":"36","author":"E Conde","year":"2008","unstructured":"Conde E (2008) A note on the minmax regret centdian location on trees. Oper Res Lett 36(2):271\u2013275","journal-title":"Oper Res Lett"},{"issue":"3","key":"213_CR31","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.tcs.2009.08.003","volume":"412","author":"W Ding","year":"2011","unstructured":"Ding W, Xue G (2011) A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. Theor Comput Sci 412(3):225\u2013232","journal-title":"Theor Comput Sci"},{"key":"213_CR32","first-page":"743908:1","volume":"2013","author":"W Ding","year":"2013","unstructured":"Ding W, Zhou Y, Chen GT, Wang HF, Wang GM (2013) On the 2-MRS problem in a tree with unreliable edges. J Appl Math 2013:743908:1\u2013743908:11","journal-title":"J Appl Math"},{"issue":"8","key":"213_CR33","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1016\/j.jcss.2010.02.001","volume":"76","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand F, Grandoni F, Rothvo\u00df T, Sch\u00e4fer G (2010) Connected facility location via random facility sampling and core detouring. J Comput Syst Sci 76(8):709\u2013726","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"213_CR34","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230220104","volume":"22","author":"E Erkut","year":"1992","unstructured":"Erkut E, Francis RL, Tamir A (1992) Distance-constrained multifacility minimax location problems on tree networks. Networks 22(1):37\u201354","journal-title":"Networks"},{"key":"213_CR35","doi-asserted-by":"crossref","unstructured":"Frederickson GN (1991) Parametric search and locating supply centers in trees. In: Proceedings of 2nd WADS, LNCS 519, pp 299\u2013319","DOI":"10.1007\/BFb0028271"},{"issue":"1","key":"213_CR36","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"GN Frederickson","year":"1983","unstructured":"Frederickson GN, Johnson DB (1983) Finding $$k$$ k th paths and $$p$$ p -centers by generating and searching good data structures. J Algorithms 4(1):61\u201380","journal-title":"J Algorithms"},{"key":"213_CR37","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. Freeman, San Francisco"},{"issue":"2","key":"213_CR38","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1287\/trsc.5.2.212","volume":"5","author":"AJ Goldman","year":"1971","unstructured":"Goldman AJ (1971) Optimal center location in simple networks. Transp Sci 5(2):212\u2013221","journal-title":"Transp Sci"},{"key":"213_CR39","doi-asserted-by":"crossref","unstructured":"Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of 33rd STOC, pp 389\u2013398","DOI":"10.1145\/380752.380830"},{"key":"213_CR40","doi-asserted-by":"crossref","unstructured":"Gupta A, Kumar A, Roughgarden T (2003) Simpler and better approximation algorithms for network design. In: Proceedings of 35th STOC, pp 365\u2013372","DOI":"10.1145\/780542.780597"},{"key":"213_CR41","doi-asserted-by":"crossref","unstructured":"Gupta A, Srinivasan A, Tardos E (2004) Cost-sharing mechanisms for network design. In: Proceedings of 7th APPROX, LNCS 3122, pp 139\u2013150","DOI":"10.1007\/978-3-540-27821-4_13"},{"issue":"3","key":"213_CR42","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1287\/trsc.7.3.287","volume":"7","author":"GY Handler","year":"1973","unstructured":"Handler GY (1973) Minimax location of a facility in an undirected tree graph. Transp Sci 7(3):287\u2013293","journal-title":"Transp Sci"},{"issue":"2","key":"213_CR43","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10878-007-9130-0","volume":"16","author":"MK Hasan","year":"2008","unstructured":"Hasan MK, Jung H, Chwa KY (2008) Approximation algorithms for connected facility location problems. J Comb Opt 16(2):155\u2013172","journal-title":"J Comb Opt"},{"issue":"6","key":"213_CR44","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1002\/net.3230230605","volume":"23","author":"SL Hakimi","year":"1993","unstructured":"Hakimi SL, Schmeichel EF, Labb\u00e9 M (1993) On locating path- or tree-shaped facilities on networks. Networks 23(6):543\u2013555","journal-title":"Networks"},{"issue":"3","key":"213_CR45","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1002\/net.3230150308","volume":"15","author":"M Jeger","year":"1985","unstructured":"Jeger M, Kariv O (1985) Algorithms for fnding $$p$$ p -centers on a weighted tree (for relatively small $$p$$ p ). Networks 15(3):381\u2013389","journal-title":"Networks"},{"key":"213_CR46","doi-asserted-by":"crossref","unstructured":"Jung H, Hasan MK, Chwa KY (2008) Improved primal-dual approximation algorithm for the connected facility location problem. In: Proceedings of 2nd COCOA, LNCS 5165, pp 265\u2013277","DOI":"10.1007\/978-3-540-85097-7_25"},{"key":"213_CR47","unstructured":"Karger DR, Minkoff M (2000) Building Steiner trees with incomplete global knowledge. In: Proceedings of 41st FOCS, pp 613\u2013623"},{"issue":"3","key":"213_CR48","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: the $$p$$ p -centers. SIAM J Appl Math 37(3):513\u2013538","journal-title":"SIAM J Appl Math"},{"issue":"3","key":"213_CR49","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. II: the $$p$$ p -medians. SIAM J Appl Math 37(3):539\u2013560","journal-title":"SIAM J Appl Math"},{"issue":"3","key":"213_CR50","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L","volume":"28","author":"TU Kim","year":"1996","unstructured":"Kim TU, Lowe TJ, Tamir A, Ward JE (1996) On the location of a tree-shaped facility. Networks 28(3):167\u2013175","journal-title":"Networks"},{"key":"213_CR51","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust discrete optimization and its applications","author":"P Kouvelis","year":"1997","unstructured":"Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, The Netherlands"},{"issue":"3","key":"213_CR52","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s00453-012-9655-1","volume":"66","author":"A Lazar","year":"2013","unstructured":"Lazar A, Tamir A (2013) Improved algorithms for some competitive location centroid problems on paths, trees and graphs. Algorithmica 66(3):615\u2013640","journal-title":"Algorithmica"},{"issue":"3","key":"213_CR53","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1287\/ijoc.8.3.194","volume":"8","author":"Y Lee","year":"1996","unstructured":"Lee Y, Chiu SY, Ryan J (1996) A branch and cut algorithm for a Steiner tree-star problem. INFORMS J Comput 8(3):194\u2013201","journal-title":"INFORMS J Comput"},{"key":"213_CR54","unstructured":"Ljubi\u0107 I (2007) A hybrid VNS for connected facility location. Hybrid metaheuristics. In: LNCS 4771, pp 157\u2013169"},{"issue":"4","key":"213_CR55","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1137\/0212051","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo N, Tamir A (1983) New results on the complexity of $$p$$ p -center problems. SIAM J Comput 12(4):751\u2013758","journal-title":"SIAM J Comput"},{"issue":"2","key":"213_CR56","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1137\/0210023","volume":"10","author":"N Megiddo","year":"1981","unstructured":"Megiddo N, Tamir A, Zemel E, Chandrasekaran R (1981) An $$O(n log^2 n)$$ O ( n l o g 2 n ) algorithm for the $$k$$ k -th longest path in a tree with applications to location problems. SIAM J Comput 10(2):328\u2013337","journal-title":"SIAM J Comput"},{"issue":"3","key":"213_CR57","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<219::AID-NET7>3.0.CO;2-L","volume":"27","author":"E Melachrinoudis","year":"1996","unstructured":"Melachrinoudis E, Helander ME (1996) A single facility location problem on a tree with unreliable edges. Networks 27(3):219\u2013237","journal-title":"Networks"},{"issue":"3","key":"213_CR58","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230150304","volume":"15","author":"E Minieka","year":"1985","unstructured":"Minieka E (1985) The optimal location of a path or tree in a tree network. Networks 15(3):309\u2013321","journal-title":"Networks"},{"issue":"3","key":"213_CR59","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0196-6774(80)90012-7","volume":"1","author":"CA Morgan","year":"1980","unstructured":"Morgan CA, Slater PL (1980) A linear time algorithm for a core of a tree. J Algorithms 1(3):247\u2013258","journal-title":"J Algorithms"},{"issue":"2","key":"213_CR60","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.20453","volume":"58","author":"J Puerto","year":"2011","unstructured":"Puerto J, Ricca F, Scozzari A (2011) Minimax regret path location on trees. Networks 58(2):147\u2013158","journal-title":"Networks"},{"issue":"4","key":"213_CR61","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.20112","volume":"47","author":"J Puerto","year":"2006","unstructured":"Puerto J, Rodr\u00edguez-Ch\u00eda AM, Tamir A, P\u00e9rez-Brito D (2006) The bi-criteria doubly weighted center-median path problem on a tree. Networks 47(4):237\u2013247","journal-title":"Networks"},{"issue":"15","key":"213_CR62","doi-asserted-by":"crossref","first-page":"2890","DOI":"10.1016\/j.dam.2007.11.022","volume":"156","author":"J Puerto","year":"2008","unstructured":"Puerto J, Tamir A, Mesa JA, P\u00e9rez-Brito D (2008) Center location problems on tree graphs with subtree-shaped customers. Discrete Appl Math 156(15):2890\u20132910","journal-title":"Discrete Appl Math"},{"issue":"1","key":"213_CR63","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1287\/opre.1050.0228","volume":"54","author":"R Ravi","year":"2006","unstructured":"Ravi R, Sinha A (2006) Approximation algorithms for problems combining facility location and network design. Oper Res 54(1):73\u201381","journal-title":"Oper Res"},{"issue":"3","key":"213_CR64","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1287\/trsc.11.3.243","volume":"11","author":"DR Shier","year":"1977","unstructured":"Shier DR (1977) A min\u2013max theorem for $$p$$ p -center problems on a tree. Transp Sci 11(3):243\u2013252","journal-title":"Transp Sci"},{"issue":"4","key":"213_CR65","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40(4):245\u2013269","journal-title":"Algorithmica"},{"issue":"1","key":"213_CR66","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1002\/net.20012","volume":"44","author":"A Tamir","year":"2004","unstructured":"Tamir A (2004) An improved algorithm for the distance constrained $$p$$ p -center location problem with mutual communication on tree networks. Networks 44(1):38\u201340","journal-title":"Networks"},{"issue":"3","key":"213_CR67","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0166-218X(00)00253-5","volume":"109","author":"A Tamir","year":"2001","unstructured":"Tamir A (2001) The $$k$$ k -centrum multi-facility location problem. Discrete Appl Math 109(3):293\u2013307","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"213_CR68","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0166-218X(98)00059-6","volume":"87","author":"A Tamir","year":"1998","unstructured":"Tamir A (1998) Fully polynomial approximation schemes for locating a tree-shaped facility: a generalization of the Knapsack problem. Discrete Appl Math 87(1\u20133):229\u2013243","journal-title":"Discrete Appl Math"},{"issue":"2","key":"213_CR69","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","volume":"19","author":"A Tamir","year":"1996","unstructured":"Tamir A (1996) An $$O(p n^2)$$ O ( p n 2 ) algorithm for the $$p$$ p -median and related problems on tree graphs. Oper Res Lett 19(2):59\u201364","journal-title":"Oper Res Lett"},{"issue":"3","key":"213_CR70","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0166-218X(93)90132-8","volume":"47","author":"A Tamir","year":"1993","unstructured":"Tamir A (1993) A unifying location model on tree graphs based on submodularity properties. Discrete Appl Math 47(3):275\u2013283","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"213_CR71","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/BF01585179","volume":"62","author":"A Tamir","year":"1993","unstructured":"Tamir A (1993) The least element property of center location on tree networks with applications to distance and precedence constrained problems. Math Program 62(1\u20133):475\u2013496","journal-title":"Math Program"},{"issue":"4","key":"213_CR72","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0404048","volume":"4","author":"A Tamir","year":"1991","unstructured":"Tamir A (1991) Obnoxious facility location on graphs. SIAM J Discrete Math 4(4):550\u2013567","journal-title":"SIAM J Discrete Math"},{"issue":"3","key":"213_CR73","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1137\/0401038","volume":"1","author":"A Tamir","year":"1988","unstructured":"Tamir A (1988) Improved complexity bounds for center location problems on networks by using dynamic data structures. SIAM J Discrete Math 1(3):377\u2013396","journal-title":"SIAM J Discrete Math"},{"issue":"3","key":"213_CR74","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/net.3230220302","volume":"22","author":"A Tamir","year":"1992","unstructured":"Tamir A, Lowe TJ (1992) The generalized $$p$$ p -forest problem on a tree network. Networks 22(3):217\u2013230","journal-title":"Networks"},{"issue":"4","key":"213_CR75","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1002\/(SICI)1097-0037(199812)32:4<255::AID-NET2>3.0.CO;2-O","volume":"32","author":"A Tamir","year":"1998","unstructured":"Tamir A, P\u00e9rez-Brito D, Moreno-P\u00e9rez JA (1998) A polynomial algorithm for the $$p$$ p -centdian problem on a tree. Networks 32(4):255\u2013262","journal-title":"Networks"},{"issue":"1","key":"213_CR76","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.jalgor.2005.01.005","volume":"56","author":"A Tamir","year":"2005","unstructured":"Tamir A, Puerto J, Mesa JA, Rodr\u00edguez-Ch\u00eda AM (2005) Conditional location of path and tree shaped facilities on trees. J Algorithms 56(1):50\u201375","journal-title":"J Algorithms"},{"issue":"3","key":"213_CR77","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0166-218X(01)00199-8","volume":"118","author":"A Tamir","year":"2002","unstructured":"Tamir A, Puerto J, P\u00e9rez-Brito D (2002) The centdian subtree on tree networks. Discrete Appl Math 118(3):263\u2013278","journal-title":"Discrete Appl Math"},{"issue":"2","key":"213_CR78","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1287\/moor.7.2.183","volume":"7","author":"A Tamir","year":"1982","unstructured":"Tamir A, Zemel E (1982) Locating centers on tree with discontinuos supply and demand regions. Math Oper Res 7(2):183\u2013197","journal-title":"Math Oper Res"},{"issue":"1","key":"213_CR79","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1287\/trsc.18.1.76","volume":"18","author":"SS Ting","year":"1984","unstructured":"Ting SS (1984) A linear-time algorithm for maxisum facility location on tree networks. Transp Sci 18(1):76\u201384","journal-title":"Transp Sci"},{"issue":"2","key":"213_CR80","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/(SICI)1520-6750(199903)46:2<147::AID-NAV2>3.0.CO;2-4","volume":"46","author":"GL Vairaktarakis","year":"1999","unstructured":"Vairaktarakis GL, Kouvelis P (1999) Incorporation dynamic aspects and uncertainty in 1-median location problems. Nav Res Logist 46(2):147\u2013168","journal-title":"Nav Res Logist"},{"issue":"2","key":"213_CR81","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s10107-006-0002-7","volume":"110","author":"S Vries","year":"2007","unstructured":"Vries S, Posner ME, Vohra RV (2007) Polyhedral properties of the $$k$$ k -median problem on a tree. Math Program 110(2):261\u2013285","journal-title":"Math Program"},{"issue":"1","key":"213_CR82","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1006\/jagm.1999.1020","volume":"34","author":"BF Wang","year":"2000","unstructured":"Wang BF (2000) Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network. J Algorithm 34(1):90\u2013108","journal-title":"J Algorithm"},{"issue":"2","key":"213_CR83","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/s00453-015-0081-z","volume":"77","author":"HL Wang","year":"2017","unstructured":"Wang HL (2017) An optimal algorithm for the weighted backup 2-center problem on a tree. Algorithmica 77(2):426\u2013439","journal-title":"Algorithmica"},{"issue":"1","key":"213_CR84","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/(SICI)1097-0037(199708)30:1<37::AID-NET5>3.0.CO;2-M","volume":"30","author":"G Xue","year":"1997","unstructured":"Xue G (1997) Linear time algorithms for computing the most reliable source on an unreliable tree network. Networks 30(1):37\u201345","journal-title":"Networks"},{"issue":"7","key":"213_CR85","doi-asserted-by":"crossref","first-page":"1159","DOI":"10.1016\/j.jcss.2015.01.002","volume":"81","author":"JH Ye","year":"2015","unstructured":"Ye JH, Wang BF (2015) On the minmax regret path median problem on trees. J Comput Syst Sci 81(7):1159\u20131170","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"213_CR86","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367076","volume":"4","author":"HI Yu","year":"2008","unstructured":"Yu HI, Lin TC, Wang BF (2008) Improved algorithms for the minmax-regret 1-center and 1-median problems. ACM Trans Algorithm 4(3):1\u201327","journal-title":"ACM Trans Algorithm"},{"key":"213_CR87","doi-asserted-by":"publisher","unstructured":"Zhou Y, Ding W, Wang G, Chen GT (2015) An edge-turbulence algorithm for the 2-MRS problem on trees with unreliable edges. Asia Pac J Oper Res. https:\/\/doi.org\/10.1142\/S0217595915400102","DOI":"10.1142\/S0217595915400102"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0213-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0213-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0213-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T09:20:51Z","timestamp":1603358451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0213-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,21]]},"references-count":87,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["213"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0213-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,11,21]]}}}