{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:27:06Z","timestamp":1759667226899},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf02098285","type":"journal-article","created":{"date-parts":[[2005,9,13]],"date-time":"2005-09-13T21:52:12Z","timestamp":1126648332000},"page":"121-141","source":"Crossref","is-referenced-by-count":16,"title":["An exact algorithm for the capacitated shortest spanning arborescence"],"prefix":"10.1007","volume":"61","author":[{"given":"Paolo","family":"Toth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Vigo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02098285_CR1","unstructured":"R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows (Prentice-Hall, 1993)."},{"key":"BF02098285_CR2","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1287\/opre.19.2.278","volume":"19","author":"M. Bellmore","year":"1971","unstructured":"M. Bellmore and J.C. Malone, Pathology of travelling salesman subtour-elimination algorithms, Operations Research 19(1971)278\u2013307.","journal-title":"Operations Research"},{"key":"BF02098285_CR3","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1002\/net.3230190505","volume":"19","author":"G. Carpaneto","year":"1989","unstructured":"G. Carpaneto, M. Dell'Amico, M. Fischetti and P. Toth, A branch and bound algorithm for the multiple depot vehicle scheduling problem, Networks 19(1989)531\u2013548.","journal-title":"Networks"},{"key":"BF02098285_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF01589105","volume":"45","author":"G. Carpaneto","year":"1989","unstructured":"G. Carpaneto, M. Fischetti and P. Toth, New lower bounds for the symmetric travelling salesman problem, Mathematical Programming 45(1989)233\u2013254.","journal-title":"Mathematical Programming"},{"key":"BF02098285_CR5","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1002\/net.3230030204","volume":"3","author":"K.M. Chandy","year":"1973","unstructured":"K.M. Chandy and T. Lo, The capacitated minimum spanning tree, Networks 3(1973)173\u2013182.","journal-title":"Networks"},{"key":"BF02098285_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Optimum branching, J. Res. Nat. Bur. Standards 71B(1967)233\u2013240.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF02098285_CR7","doi-asserted-by":"crossref","first-page":"1753","DOI":"10.1109\/TCOM.1974.1092122","volume":"COM-22","author":"D. Elias","year":"1974","unstructured":"D. Elias and M.J. Ferguson, Topological design of multipoint teleprocessing networks, IEEE Transactions on Communications COM-22(1974)1753\u20131762.","journal-title":"IEEE Transactions on Communications"},{"key":"BF02098285_CR8","volume-title":"Vehicle Routing: Methods and Studies","author":"M. Fischetti","year":"1988","unstructured":"M. Fischetti and P. Toth, An additive approach for the optimal solution of the prize-collecting travelling salesman problem, in:Vehicle Routing: Methods and Studies, eds. B.L. Golden and A.A. Assad (North-Holland, Amsterdam, 1988)."},{"key":"BF02098285_CR9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0167-6377(88)90025-9","volume":"7","author":"M. Fischetti","year":"1988","unstructured":"M. Fischetti and P. Toth, A new dominance procedure for combinatorial optimization problems, Operations Research Letters 7(1988)181\u2013187.","journal-title":"Operations Research Letters"},{"key":"BF02098285_CR10","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/opre.37.2.319","volume":"37","author":"M. Fischetti","year":"1989","unstructured":"M. Fischetti and P. Toth, An Additive Bounding Procedure for Combinatorial Optimization Problems, Operations Research 37(1989)319\u2013328.","journal-title":"Operations Research"},{"key":"BF02098285_CR11","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01585701","volume":"53","author":"M. Fischetti","year":"1992","unstructured":"M. Fischetti and P. Toth, An additive bounding procedure for the asymmetric travelling salesman problem, Mathematical Programming 53(1992)173\u2013197.","journal-title":"Mathematical Programming"},{"key":"BF02098285_CR12","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1287\/ijoc.5.4.426","volume":"5","author":"M. Fischetti","year":"1993","unstructured":"M. Fischetti and P. Toth, An efficient algorithm for the min-sum arborescence problem on complete digraphs, ORSA Journal on Computing 5(1993)426\u2013434.","journal-title":"ORSA Journal on Computing"},{"key":"BF02098285_CR13","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/opre.42.5.846","volume":"42","author":"M. Fischetti","year":"1994","unstructured":"M. Fischetti, P. Toth and D. Vigo, A branch and bound algorithm for the capacitated vehicle routing problem on directed graphs, Operations Research 42(1994)846\u2013859.","journal-title":"Operations Research"},{"key":"BF02098285_CR14","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"M.L. Fisher","year":"1994","unstructured":"M.L. Fisher, Optimal solution of vehicle routing problems using minimumk-trees, Operations Research 42(1994)626\u2013642.","journal-title":"Operations Research"},{"key":"BF02098285_CR15","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0196-6774(84)90042-7","volume":"5","author":"H.N. Gabow","year":"1984","unstructured":"H.N. Gabow and R.E. Tarjan, Efficient algorithms for a family of matroid intersection problems, Journal of Algorithms 5(1984)80\u2013131.","journal-title":"Journal of Algorithms"},{"key":"BF02098285_CR16","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/322358.322367","volume":"30","author":"B. Gavish","year":"1983","unstructured":"B. Gavish, Formulations and algorithms for the capacitated minimal directed tree problem, Journal of the Association for Computing Machinery 30(1983)118\u2013132.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02098285_CR17","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1002\/net.3230040403","volume":"4","author":"A. Kershenbaum","year":"1974","unstructured":"A. Kershenbaum, Computing capacitated minimal spanning trees efficiently, Networks 4(1974)299\u2013310.","journal-title":"Networks"},{"key":"BF02098285_CR18","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees, Operations Research 18(1970)1138\u20131162.","journal-title":"Operations Research"},{"key":"BF02098285_CR19","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees: Part II, Mathematical Programming 1(1971)6\u201325.","journal-title":"Mathematical Programming"},{"key":"BF02098285_CR20","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"S. Martello and P. Toth,Knapsack Problems: Algorithms and Computer Implementations (Wiley, Chichester, 1990)."},{"key":"BF02098285_CR21","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1002\/net.3230230603","volume":"23","author":"K. Malik","year":"1993","unstructured":"K. Malik and G. Yu, A branch and bound algorithm for the capacitated minimum spanning tree problem, Networks 23(1993)525\u2013532.","journal-title":"Networks"},{"key":"BF02098285_CR22","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/net.3230080306","volume":"8","author":"C.H. Papadimitriou","year":"1978","unstructured":"C.H. Papadimitriou, The complexity of the capacitated tree problem, Networks 8(1978)217\u2013230.","journal-title":"Networks"},{"key":"BF02098285_CR23","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R.E. Tarjan","year":"1977","unstructured":"R.E. Tarjan, Finding optimum branchings, Networks 7(1977)25\u201335.","journal-title":"Networks"},{"key":"BF02098285_CR24","unstructured":"P. Toth and D. Vigo, An exact algorithm for the vehicle routing problem with backhauls, Research Report, DEIS OR\/93\/5, University of Bologna (1993)."},{"key":"BF02098285_CR25","unstructured":"G. Yu and M.L. Fisher, A Lagrangian optimization algorithm for the asymmetric non-uniform fleet vehicle routing problem, Working Paper 89-03-10, Decision Science Department, The Wharton School, University of Pennsylvania (1989)."},{"key":"BF02098285_CR26","unstructured":"D. Vigo, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, European Journal of Operational Research, to appear."},{"key":"BF02098285_CR27","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/net.3230160104","volume":"16","author":"G. Laporte","year":"1986","unstructured":"G. Laporte, H. Mercure and Y. Nobert, An exact algorithm for the asymmetrical capacitated vehicle routing problem, Networks 16(1986)33\u201346.","journal-title":"Networks"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02098285.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02098285\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02098285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T14:29:29Z","timestamp":1557844169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02098285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF02098285"],"URL":"https:\/\/doi.org\/10.1007\/bf02098285","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}