{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T00:19:10Z","timestamp":1673482750710},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540610434","type":"print"},{"value":"9783540498759","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0027120","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"115-144","source":"Crossref","is-referenced-by-count":4,"title":["Mapping tree-structured combinatorial optimization problems onto parallel computers"],"prefix":"10.1007","author":[{"given":"Reinhard","family":"L\u00fcling","sequence":"first","affiliation":[]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Reinefeld","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Tsch\u00f6ke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"6_CR1","unstructured":"S. Arvindam, V. Kumar and V. Rao. Efficient parallel algorithms for searching problems: Applications in VLSI CAD. 3rd Symp. Frontiers Mass. Par. Comp., Maryland (1990), 166\u2013169."},{"key":"6_CR2","unstructured":"R. D. Blumofe, C. E. Leiseron. Scheduling Multithreaded Computations by Work Stealing. Foundations of Computer Science, 1994"},{"issue":"1","key":"6_CR3","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1287\/opre.25.1.30","volume":"25","author":"N. Christofides","year":"1977","unstructured":"N. Christofides and C. Whitlock. An algorithm for two-dimensional cutting problems. Operations Research 25, 1 (1977), 30\u201344.","journal-title":"Operations Research"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian and T. van Eicken. LogP: Towards a realistic model of parallel computation. ACM SIGPLAN Symp. Principles and Practice of Parallel Programming, San Diego, (May 1993).","DOI":"10.1145\/155332.155333"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0020-0190(83)90092-3","volume":"16","author":"E. Dijkstra","year":"1983","unstructured":"E. Dijkstra, W.H.J. Feijen and A.J.M. van Gasteren. Derivation of a termination detection algorithm for distributed computation. Inf. Proc. Lett. 16 (1983), 217\u2013219.","journal-title":"Inf. Proc. Lett."},{"key":"6_CR6","unstructured":"O.I. El-Dessouki and W.H. Huen. Distributed enumeration on network computers. Procs. 1979 Intern. Conf. Par. Proc., 137\u2013146."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"D. Ferguson, Y. Yemini, C. Nikolaou. Microeconomic Algorithms for Load Balancing in Distributed Computer Systems. Proc. IEEE 8 th Int. Conf. on Distributed Computing Systems 1988, pp. 539\u2013546.","DOI":"10.1109\/DCS.1988.12552"},{"key":"6_CR8","unstructured":"R. Finkel and U. Manber. DIB \u2014 A distributed implementation of backtracking. 5th Conf. Distr. Comp. Systems, Denver, 1985, 446\u2013452."},{"key":"6_CR9","first-page":"129","volume-title":"Encyclopedia of Microcomputers, Vol. 13","author":"A. Grama","year":"1993","unstructured":"A. Grama, V. Kumar and P. Pardalos. Parallel Processing of Discrete Optimization Problems. Encyclopedia of Microcomputers, Vol. 13 (1993), pp. 129\u2013147, Marcel Dekker Inc., New York."},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/jpdc.1993.1107","volume":"19","author":"A. Gupta","year":"1993","unstructured":"A. Gupta and V. Kumar. Performance properties of large scale parallel systems. J. Parallel and Distributed Comp., 19(1993), 234\u2013244.","journal-title":"J. Parallel and Distributed Comp."},{"key":"6_CR11","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 traveling salesman problem and minimum spanning trees. Operations Research 18 (1970), 1138\u20131162.","journal-title":"Operations Research"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R.M. Karp, The traveling salesman problem and minimum spanning trees: part II, Mathematical Programming 1 (1971) 6\u201325","journal-title":"Mathematical Programming"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0743-7315(90)90025-K","volume":"10","author":"S. H. Hosseini","year":"1990","unstructured":"S. H. Hosseini, B. Litow, M. Malkawi, J. Mepherson, K. Vairavan. Analysis of a graph coloring based distributed load balancing algorithm. Journal of Parallel and Distributed Computing, vol 10, 1990, pp. 160\u2013166","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF02186483","volume":"14","author":"G.A.P. Kindervater","year":"1988","unstructured":"G.A.P. Kindervater and J.K. Lenstra. Parallel computing in Combinatorial Optimization. Annals of Operations Research 14, 1988, 245\u2013289.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"6_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0004-3702(75)90019-3","volume":"6","author":"D.E. Knuth","year":"1975","unstructured":"D.E. Knuth and R.W. Moore. An analysis of alpha-beta pruning. Artif. Intell. 6,4(1975), 293\u2013326.","journal-title":"Artif. Intell."},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"R.E. Korf","year":"1985","unstructured":"R.E. Korf. Depth-first iterative-deepening: An optimal admissible tree search. Art. Intell. 27 (1985), 97\u2013109.","journal-title":"Art. Intell."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"V. Kumar and V. Rao. Scalable parallel formulations of depth-first search. Kumar, Gopalakrishnan, Kanal, eds., Par. Alg. for Mach. Intell. and Vision, Springer 1990, 1\u201341.","DOI":"10.1007\/978-1-4612-3390-9_1"},{"key":"6_CR18","volume-title":"Introduction to Parallel Computing. Design and Analysis of Algorithms","author":"V. Kumar","year":"1994","unstructured":"V. Kumar, A. Grama, A. Gupta and G. Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin\/Cummings Publ., Redwood City, CA (1994)."},{"key":"6_CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/978-1-4613-8788-6_3","volume-title":"Search in Artificial Intelligence","author":"V. Kumar","year":"1988","unstructured":"V. Kumar, D.S. Nau and L. Kanal. A general branch-and-bound formulation for AND\/OR graph and game-tree search. In L. Kanal, V. Kumar (eds.), Search in Artificial Intelligence. Springer-Verlag, Berlin (1988), 91\u2013130."},{"key":"6_CR20","first-page":"600","volume":"14","author":"E.L. Lawler","year":"1966","unstructured":"E.L. Lawler and D.E. Wood. Branch and Bound methods: A survey. Operations Research 14 (1966), 600\u2013719.","journal-title":"Operations Research"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"R. L\u00fcling and B. Monien. Load balancing for distributed branch & bound algorithms. Intern. Par. Processing Symp., IPPS 1992.","DOI":"10.1109\/IPPS.1992.222970"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"R. L\u00fcling, B. Monien and F. Ramme. Load Balancing in Large Networks: A Comparative Study. Proc. of 3rd IEEE Symp. on Parallel and Distributed Processing, 1991","DOI":"10.1109\/SPDP.1991.218196"},{"key":"6_CR23","unstructured":"R. L\u00fcling, B. Monien and S. Tsch\u00f6cke. Load balancing for distributed branch & bound algorithms: Experiments and theory. DIMACS Workshop \u201cParallel Processing of Discrete Optimization Problems\u201d, (April 1994)."},{"key":"6_CR24","unstructured":"A. Mahanti, S. Ghosh, D.S. Nau, A.K. Pal and L. Kanal. Performance of IDA* on trees and graphs. 10th Nat. Conf. on Art. Int., AAAI-92, San Jose, (1992), 539\u2013544."},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0377-2217(92)90212-R","volume":"58","author":"R.N. Morabito","year":"1992","unstructured":"R.N. Morabito, M.N. Arenales and V.F. Arcaro. An and-or-graph approach for two dimensional cutting problems. Europ. J. Oper. Res. 58 (1992), 263\u2013271.","journal-title":"Europ. J. Oper. Res."},{"key":"6_CR26","volume-title":"Principles of Artificial Intelligence","author":"N.J. Nilsson","year":"1980","unstructured":"N.J. Nilsson. Principles of Artificial Intelligence. Tioga Publ., Palo Alto, CA, 1980."},{"key":"6_CR27","unstructured":"C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982."},{"key":"6_CR28","unstructured":"P. M. Pardalos, A. Phillips and J.B. Rosen. Topics in Parallel Computing in Mathematical Programming. Science Press, (1992)."},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"P.M. Pardalos M.G.C. Resende and K.G. Ramakrishnan (Editors). Parallel Processing of Discrete Optimization Problems. DIMACS Series, American Mathematical Society, (1995).","DOI":"10.1090\/dimacs\/022"},{"key":"6_CR30","volume-title":"Heuristics. Intelligent Search Strategies for Computer Problem Solving","author":"J. Pearl","year":"1984","unstructured":"J. Pearl. Heuristics. Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, MA, (1984)."},{"issue":"5","key":"6_CR31","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1109\/34.134045","volume":"PAMI-13","author":"C. Powley","year":"1991","unstructured":"C. Powley and R.E. Korf. Single-agent parallel window search. IEEE Trans. Pattern Anal. Mach. Int., PAMI-13,5 (1991), 466\u2013477.","journal-title":"IEEE Trans. Pattern Anal. Mach. Int."},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"A. Ranade. Optimal speedup for backtracking search on a butterfly network. Procs. 3rd ACM Symp. Parallel Alg. and Architect. (1991), 40\u201348.","DOI":"10.1145\/113379.113383"},{"key":"6_CR33","unstructured":"V.N. Rao, V. Kumar and K. Ramesh. A parallel implementation of iterative-deepening A*. AAAI-87, 878\u2013882."},{"issue":"4","key":"6_CR34","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1109\/71.219757","volume":"4","author":"V.N. Rao","year":"1993","unstructured":"V.N. Rao and V. Kumar. On the efficiency of parallel backtracking. IEEE Trans. Par. Distr. Systems 4,4(1993), 427\u2013437.","journal-title":"IEEE Trans. Par. Distr. Systems"},{"key":"6_CR35","unstructured":"D. Ratner and M. Warmuth. Finding a shortest solution for the N\u00d7N extension of the 15-puzzle is intractable. AAAI-86, 168\u2013172."},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"A. Reinefeld and T.A. Marsland. Enhanced iterative-deepening search. IEEE Trans. Pattern Analysis Mach. Intell., IEEE-PAMI, July 1994.","DOI":"10.1109\/34.297950"},{"key":"6_CR37","first-page":"295","volume-title":"AIDA* \u2014 Asynchronous Parallel IDA*","author":"A. Reinefeld","year":"1994","unstructured":"A. Reinefeld and V. Schnecke. AIDA* \u2014 Asynchronous Parallel IDA*. Procs. 10th Canadian Conf. on Art. Intell. AI'94, (May 1994), Banff, Canada, Morgan Kaufman, 295\u2013302."},{"key":"6_CR38","unstructured":"A. Reinefeld and V. Schnecke. Work-load balancing in highly parallel depth-first search. Procs. Scalable High Perf. Comp. Conf. SHPCC'94, Knoxville, Te, 773\u2013780."},{"key":"6_CR39","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"G. Reinelt. TSPLIB \u2014 A Traveling Salesman Problem Library. ORSA Journal on Computing, 3 1991, pp. 376\u2013284","journal-title":"ORSA Journal on Computing"},{"key":"6_CR40","unstructured":"V. Saletore and L.V. Kale. Consistent linear speedup to a first solution in parallel state-space search. Procs. 1990 Nat. Conf. Artif. Intell. (1990), 227\u2013233."},{"key":"6_CR41","unstructured":"J.A. Stankovic, I.S. Sidhu. An Adaptive Bidding Algorithm for Processes, Clusters and Distributed Groups. Proc. IEEE 4 th Int. Conf. on Distributed Computing Systems 1984, pp. 49\u201359"},{"issue":"2","key":"6_CR42","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0004-3702(79)90016-X","volume":"12","author":"G.C. Stockman","year":"1979","unstructured":"G.C. Stockman. A minimax algorithm faster than alpha-beta? Artificial Intelligence 12,2(1979), 179\u2013196","journal-title":"Artificial Intelligence"},{"key":"6_CR43","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0019-9958(83)80038-2","volume":"57","author":"L. Stockmeyer","year":"1983","unstructured":"L. Stockmeyer. Optimal orientations of cells in silicon floorplan designs. Inform. and Control 57 (1983), 97\u2013101.","journal-title":"Inform. and Control"},{"key":"6_CR44","doi-asserted-by":"crossref","unstructured":"S. Tsch\u00f6ke, R. L\u00fcling, B. Monien. Solving the Traveling Salesman Problem with a Distributed Branch and Bound Algorithm on a 1024 Processor Network. Proc. of Int. Parallel Processing Symposium (IPPS), 1995.","DOI":"10.1109\/IPPS.1995.395930"},{"key":"6_CR45","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0377-2217(82)90015-7","volume":"9","author":"T. Volgenant","year":"1982","unstructured":"T. Volgenant, R. Jonker, A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European J. Operational Res. 9 (1982) 83\u201389","journal-title":"European J. Operational Res."},{"key":"6_CR46","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/0377-2217(83)90161-3","volume":"12","author":"T. Volgenant","year":"1983","unstructured":"T. Volgenant, R. Jonker, The symmetric traveling salesman problem and edge exchange in minimal 1-trees, European J. Operational Res. 12 (1983) 394\u2013403","journal-title":"European J. Operational Res."},{"issue":"No.4","key":"6_CR47","first-page":"65","volume":"32","author":"T. Volgenant","year":"1984","unstructured":"T. Volgenant, R. Jonker, Nonoptimal Edges for the Symmetric Traveling Salesman Problem, Operations Research Vol. 32 No. 4 (1984) 65\u201374","journal-title":"Operations Research"},{"key":"6_CR48","doi-asserted-by":"crossref","unstructured":"S. Wimer, I. Koren and I. Cederbaum. Optimal aspect ratios of building blocks in VLSI. 25th ACM\/IEEE Design Automation Conference, (1988), 66\u201372.","DOI":"10.1109\/DAC.1988.14736"},{"key":"6_CR49","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0743-7315(92)90021-E","volume":"16","author":"C. Z. Xu","year":"1992","unstructured":"C. Z. Xu, F.C.M. Lau. Analysis of the generalized dimension exchange method for dynamic load balancing. Journal of Parallel and Distributed Computing, vol 16, 1992, pp. 385\u2013393","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"6_CR50","unstructured":"C. Z. Xu, B. Monien, R. L\u00fcling, F.C.M. Lau. An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers. Proc of Int. Parallel Processing Symposium (IPPS), 1995"}],"container-title":["Solving Combinatorial Optimization Problems in Parallel","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0027120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T01:57:58Z","timestamp":1586570278000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":50,"URL":"http:\/\/dx.doi.org\/10.1007\/bfb0027120","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1996]]}}}