{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:05:38Z","timestamp":1747548338788},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1991,5,1]],"date-time":"1991-05-01T00:00:00Z","timestamp":673056000000},"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":[[1991,5]]},"DOI":"10.1007\/bf02073942","type":"journal-article","created":{"date-parts":[[2005,8,13]],"date-time":"2005-08-13T11:06:02Z","timestamp":1123931162000},"page":"379-402","source":"Crossref","is-referenced-by-count":11,"title":["Branch-and-bound as a higher-order function"],"prefix":"10.1007","volume":"33","author":[{"given":"G. P.","family":"McKeown","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. J.","family":"Rayward-Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. J.","family":"Turpin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02073942_CR1","doi-asserted-by":"crossref","first-page":"B176","DOI":"10.1287\/mnsc.13.4.B176","volume":"13","author":"N. Agin","year":"1966","unstructured":"N. Agin, Optimum seeking with branch-and-bound, Manag. Sci. 13(1966)B176-B185.","journal-title":"Manag. Sci."},{"key":"BF02073942_CR2","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman,Data Structures and Algorithms (Addison-Wesley, 1982)."},{"key":"BF02073942_CR3","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1002\/net.3230170107","volume":"17","author":"A. Balakrishnan","year":"1987","unstructured":"A. Balakrishnan and N.R. Patel, Problem reduction methods and a tree generation algorithm for the Steiner network problem, Networks 17(1987)65\u201385.","journal-title":"Networks"},{"key":"BF02073942_CR4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1287\/opre.13.4.517","volume":"13","author":"E. Balas","year":"1965","unstructured":"E. Balas, An additive algorithm for solving linear programs with zero-one variables, Oper. Res. 13(1965)517\u2013526.","journal-title":"Oper. Res."},{"key":"BF02073942_CR5","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1287\/opre.16.2.442","volume":"16","author":"E. Balas","year":"1968","unstructured":"E. Balas, A note on the branch-and-bound principle, Oper. Res. 16(1968)442\u2013445.","journal-title":"Oper. Res."},{"key":"BF02073942_CR6","first-page":"361","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"E. Balas","year":"1985","unstructured":"E. Balas and P. Toth, Branch and bound methods, in:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. Lawler, Lenstra, Rinnooy Kan and Shmoys (Wiley, London, 1985), pp. 361\u2013401."},{"key":"BF02073942_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230190102","volume":"19","author":"J.E. Beasley","year":"1989","unstructured":"J.E. Beasley, An SST-based algorithm for the Steiner problem in graphs, Networks 19(1989)1\u201316.","journal-title":"Networks"},{"key":"BF02073942_CR8","unstructured":"F.W. Burton, G.P. McKeown, V.J. Rayward-Smith and M.R. Sleep, Parallel processing and combinatorial optimisation,Proc. CO81 Conf., Stirling University (1982)."},{"key":"BF02073942_CR9","unstructured":"J. Clausen and J.L. Tr\u00e4ff, Implementation of parallel branch-and-bound algorithms \u2014 experiences with the graph partitioning problem, NATO\/ARW on Topological Network Design, Copenhagen (1989), Ann. Oper. Res., this volume."},{"key":"BF02073942_CR10","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1093\/comjnl\/8.3.250","volume":"8","author":"R.J. Dakin","year":"1965","unstructured":"R.J. Dakin, A tree-search algorithm for mixed-integer programming problems, Comp. J. 8(1965)250\u2013255.","journal-title":"Comp. J."},{"key":"BF02073942_CR11","unstructured":"C.W. Duin and A. Volgenaut, Reduction tests for the Steiner problem in graphs, Department of Operations Research, Faculty of Economic Sciences and Econometrics, University of Amsterdam (1988)."},{"key":"BF02073942_CR12","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/22719.24067","volume":"9","author":"R. Finkel","year":"1987","unstructured":"R. Finkel and U. Manber, DIB \u2014 a distributed implementation of backtracking, ACM Trans. Prog. Languages and Systems 9(1987)235\u2013256.","journal-title":"ACM Trans. Prog. Languages and Systems"},{"key":"BF02073942_CR13","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P.E. Hart","year":"1968","unstructured":"P.E. Hart, N. Nilsson and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Systems and Cybernetics 4(1968)100\u2013107.","journal-title":"IEEE Trans. Systems and Cybernetics"},{"key":"BF02073942_CR14","volume-title":"Fundamentals of Computer Algorithms","author":"E. Horowitz","year":"1978","unstructured":"E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms (Computer Science Press, Rockville, MD, 1978)."},{"key":"BF02073942_CR15","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1093\/comjnl\/32.2.98","volume":"32","author":"R.J.M. Hughes","year":"1989","unstructured":"R.J.M. Hughes, Why functional programming matters, Comp. J. 32(1989)98\u2013107.","journal-title":"Comp. J."},{"key":"BF02073942_CR16","unstructured":"F.K. Hwang and D. Richards, a two-volume collection of important works in the area of Steiner trees, to appear in the series:Advances in Discrete Mathematics and Computer Science (Hadronic Press)."},{"key":"BF02073942_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(78)90197-3","volume":"36","author":"T. Ibaraki","year":"1978","unstructured":"T. Ibaraki, Branch-and-bound procedure and state-space representation of combinatorial optimization problems, Information and Control 36(1978)1\u201327.","journal-title":"Information and Control"},{"key":"BF02073942_CR18","doi-asserted-by":"crossref","unstructured":"T. Ibaraki, Implementation and concurrent execution of branch-and-bound algorithms, Ann. Oper. Res. 10\/11(1987), ch. 9.","DOI":"10.1007\/BF02188551"},{"key":"BF02073942_CR19","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher (Plenum Press, New York, 1972), pp. 85\u2013103."},{"key":"BF02073942_CR20","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1145\/321796.321808","volume":"21","author":"W.H. Kohler","year":"1974","unstructured":"W.H. Kohler and K. Steiglitz, Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, J. ACM 21(1974)140\u2013156.","journal-title":"J. ACM"},{"key":"BF02073942_CR21","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0004-3702(83)80009-5","volume":"21","author":"V. Kumar","year":"1983","unstructured":"V. Kumar and L.N. Kanal, A general branch-and-bound formulation for understanding and synthesizing AND\/OR tree search procedures, Artificial Intelligence 21(1983)179\u2013198.","journal-title":"Artificial Intelligence"},{"key":"BF02073942_CR22","doi-asserted-by":"crossref","unstructured":"T.H. Lai and S. Sahni, Anomalies in parallel branch-and-bound algorithms, CACM 27(1984).","DOI":"10.1145\/358080.358103"},{"key":"BF02073942_CR23","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(86)90109-2","volume":"23","author":"T.H. Lai","year":"1986","unstructured":"T.H. Lai and A. Sprague, A note on anomalies in parallel branch-and-bound algorithms with one-to-one bounding functions, Inf. Proc. Lett. 23(1986)119\u2013122.","journal-title":"Inf. Proc. Lett."},{"key":"BF02073942_CR24","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"A.H. Land","year":"1960","unstructured":"A.H. Land and A.G. Doig, An automatic method of solving discrete programming problems, Econometrica 28(1960)497\u2013520.","journal-title":"Econometrica"},{"key":"BF02073942_CR25","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"E.L. Lawler","year":"1966","unstructured":"E.L. Lawler and D.E. Wood, Branch-and-bound methods: A survey, Oper. Res. 14(1966)699\u2013719.","journal-title":"Oper. Res."},{"key":"BF02073942_CR26","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1109\/TC.1986.5009434","volume":"C-35","author":"G.-J. Li","year":"1986","unstructured":"G.-J. Li and B.W. Wah, Coping with anomalies in parallel branch-and-bound algorithms, IEEE Trans. Comp. C-35(1986)568\u2013573.","journal-title":"IEEE Trans. Comp."},{"key":"BF02073942_CR27","unstructured":"G.-J. Li and B.W. Wah, Computational efficiency of parallel approximate branch-and-bound algorithms,Proc. 1984 Int. Conf. on Parallel Processing (1984), pp. 473\u2013480."},{"key":"BF02073942_CR28","unstructured":"I. Marshall and P. Messer, Conventions for generic abstract data type modules in Modula-2, School of Information Systems, University of East Anglia, Norwich, in preparation."},{"key":"BF02073942_CR29","unstructured":"G.P. McKeown, V.J. Rayward-Smith, S.A. Rush and H.J. Turpin, A framework for the implementation of parallel integer programming branch-and-bound on a transputer rack, submitted for publication."},{"key":"BF02073942_CR30","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/opre.18.1.24","volume":"18","author":"L.G. Mitten","year":"1970","unstructured":"L.G. Mitten, Branch-and-bound methods: General formulation and properties, Oper. Res. 18(1970)24\u201334.","journal-title":"Oper. Res."},{"key":"BF02073942_CR31","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0004-3702(84)90004-3","volume":"23","author":"D.S. Nau","year":"1984","unstructured":"D.S. Nau, V. Kumar and L. Kanal, General branch-and-bound, and its relation to A* and AO*, Artificial Intelligence 23(1984)29\u201358.","journal-title":"Artificial Intelligence"},{"key":"BF02073942_CR32","volume-title":"Problem-solving Methods in Artificial Intelligence","author":"N.J. Nilsson","year":"1971","unstructured":"N.J. Nilsson,Problem-solving Methods in Artificial Intelligence (McGraw-Hill, New York, 1971)."},{"key":"BF02073942_CR33","first-page":"155","volume":"31","author":"J. Plesnik","year":"1981","unstructured":"J. Plesnik, A bound for the Steiner tree problem in graphs, Math. Slovaca 31(1981)155\u2013163.","journal-title":"Math. Slovaca"},{"key":"BF02073942_CR34","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"R.C. Prim, Shortest connection networks and some generalizations, Bell. Syst. Tech. J. 36(1957)1389\u20131401.","journal-title":"Bell. Syst. Tech. J."},{"key":"BF02073942_CR35","volume-title":"Designing Efficient Algorithms for Parallel Computers","author":"M.J. Quinn","year":"1987","unstructured":"M.J. Quinn,Designing Efficient Algorithms for Parallel Computers (McGraw-Hill, New York, 1987)."},{"key":"BF02073942_CR36","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/0020739830140103","volume":"14","author":"V.J. Rayward-Smith","year":"1983","unstructured":"V.J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs, Int. J. Math. Educ. Sci. Tech. 14(1983)15\u201323.","journal-title":"Int. J. Math. Educ. Sci. Tech."},{"key":"BF02073942_CR37","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/net.3230160305","volume":"16","author":"V.J. Rayward-Smith","year":"1986","unstructured":"V.J. Rayward-Smith and A. Clare, On finding Steiner vertices, Networks 16(1986)283\u2013294.","journal-title":"Networks"},{"key":"BF02073942_CR38","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF03037504","volume":"6","author":"V.J. Rayward-Smith","year":"1988","unstructured":"V.J. Rayward-Smith, G.P. McKeown and F.W. Burton, The general problem solving algorithm and its implementation, New Generation Computing 6(1988)41\u201366.","journal-title":"New Generation Computing"},{"key":"BF02073942_CR39","volume-title":"Combinatorial Algorithms: Theory and Practice","author":"E.M. Reingold","year":"1977","unstructured":"E.M. Reingold, J. Nievergelt and N. Deo,Combinatorial Algorithms: Theory and Practice (Prentice-Hall, Englewood Cliffs, NJ, 1977)."},{"key":"BF02073942_CR40","volume-title":"Mathematical Programming: Structures and Algorithms","author":"J.F. Shapiro","year":"1979","unstructured":"J.F. Shapiro,Mathematical Programming: Structures and Algorithms (Wiley, New York, 1979)."},{"key":"BF02073942_CR41","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230120309","volume":"12","author":"M.L. Shore","year":"1982","unstructured":"M.L. Shore, L.R. Foulds and P.B. Gibbons, An algorithm for the Steiner problem in graphs, Networks 12(1982)323\u2013333.","journal-title":"Networks"},{"key":"BF02073942_CR42","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica 24(1980)573\u2013577.","journal-title":"Math. Japonica"},{"key":"BF02073942_CR43","volume-title":"The branch-and-bound paradigm","author":"H.J. Turpin","year":"1990","unstructured":"H.J. Turpin, The branch-and-bound paradigm, Ph.D. Thesis, School of Information Systems, University of East Anglia, Norwich (1990)."},{"key":"BF02073942_CR44","unstructured":"H.J. Turpin, G.P. McKeown, V.J. Rayward-Smith and S.A. Rush, Branch-and-bound on a transputer rack, submitted for publication."},{"key":"BF02073942_CR45","doi-asserted-by":"crossref","unstructured":"B.W. Wah, G.-J. Li and C.F. Yu, Multiprocessing of combinatorial search problems, IEEE Computer 18(1985).","DOI":"10.1109\/MC.1985.1662926"},{"key":"BF02073942_CR46","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1109\/TC.1984.1676453","volume":"C-33","author":"B.W. Wah","year":"1984","unstructured":"B.W. Wah and Y.W.E. Ma, MANIP \u2014 a multicomputer architecture for solving combinatorial extremum-search problems, IEEE Trans. Comp. C-33(1984)377\u2013390.","journal-title":"IEEE Trans. Comp."},{"key":"BF02073942_CR47","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0020-0190(88)90225-6","volume":"29","author":"B.M. Waxman","year":"1988","unstructured":"B.M. Waxman and M. Imase, Worst-case performance of Rayward-Smith's Steiner tree heuristic, Inf. Proc. Lett. 29(1988)283\u2013287.","journal-title":"Inf. Proc. Lett."},{"key":"BF02073942_CR48","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Y.F. Wu","year":"1986","unstructured":"Y.F. Wu, P. Widmayer and C.K. Wong, A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica 23(1986)223\u2013229.","journal-title":"Acta Informatica"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02073942.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02073942\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02073942","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T23:46:21Z","timestamp":1586389581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02073942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["BF02073942"],"URL":"https:\/\/doi.org\/10.1007\/bf02073942","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,5]]}}}