{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:12Z","timestamp":1725460032224},"publisher-location":"Berlin\/Heidelberg","reference-count":23,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540582770"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0049327","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:58:16Z","timestamp":1141671496000},"page":"106-127","source":"Crossref","is-referenced-by-count":0,"title":["On the reasons for average superlinear speedup in parallel backtrack search"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Goerdt","sequence":"first","affiliation":[]},{"given":"Udo","family":"Kamps","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"B. Monien, E. Speckenmeyer, O. Vornberger, Superlinear speedup for parallel backtracking, Technical Report No 30, Dept. of Math. and Comp. Sci. University of Paderborn, 1986.","key":"8_CR1"},{"key":"8_CR2","first-page":"985","volume":"297","author":"E. Speckenmeyer","year":"1987","unstructured":"E. Speckenmeyer, B. Monien, O. Vornberger, Superlinear speedup for parallel backtracking, Proc. Supercomputing 1987, LNCS 297, 985\u2013993.","journal-title":"LNCS"},{"key":"8_CR3","first-page":"301","volume":"385","author":"E. Speckenmeyer","year":"1988","unstructured":"E. Speckenmeyer, Is average superlinear speedup possible? Proc. 2nd Workshop on Comp. Sci. Logic 1988, LNCS 385, 301\u2013312.","journal-title":"LNCS"},{"key":"8_CR4","first-page":"161","volume":"338","author":"V.N. Rao","year":"1988","unstructured":"V.N. Rao, V. Kumar, Superlinear speedup in parallel state space search, Proc. 8th Conf. on Foundations of Software Technology and Theoretical Comp. Sci. 1988, LNCS 338, 161\u2013174.","journal-title":"LNCS"},{"key":"8_CR5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF02186483","volume":"14","author":"G.A.P. Kindervater","year":"1988","unstructured":"G.A.P. Kindervater, J.K. Lenstra, Parallel computing in Combinatorial Optimization, Annals of OR 14, 1988, 245\u2013289.","journal-title":"Annals of OR"},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF00127952","volume":"5","author":"S. Chakravarty","year":"1992","unstructured":"S. Chakravarty, A. Shekhawat, Parallel and serial heuristics for the minimum set cover problem, Journal of Supercomputing 5, 1992, 331\u2013345.","journal-title":"Journal of Supercomputing"},{"unstructured":"W. Ertel, Parallele Suche mit randomisiertem Wettbewerb in Inferenzsystemen. PhD Thesis, Technical University of Munich, 1992.","key":"8_CR7"},{"issue":"2","key":"8_CR8","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1109\/71.80148","volume":"1","author":"D.P. Helmbold","year":"1990","unstructured":"D.P. Helmbold, C.E. McDowall, Modeling Speedup(n) greater than n, IEEE Trans. on Par. and Distr. Systems, 1(2), 1990, 250\u2013256.","journal-title":"IEEE Trans. on Par. and Distr. Systems"},{"unstructured":"R. Mehrotra, E.F. Geringer, Superlinear speedup through randomized algorithms, Proc. Conf. on Parallel Processing 1985, 291\u2013300.","key":"8_CR9"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0166-218X(83)90017-3","volume":"5","author":"J. Franco","year":"1983","unstructured":"J. Franco, M. Paull, Probabilistic analysis of the Davis-Putnam procedure for the satisfiability problem, Discr. Appl. Math. 5, 1983, 77\u201387.","journal-title":"Discr. Appl. Math."},{"key":"8_CR11","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1137\/0210043","volume":"10","author":"C.A. Brown","year":"1981","unstructured":"C.A. Brown, P.W. Purdom, An average time analysis of backtracking, SIAM Jour. on Comp. 10, 1981, 583\u2013593.","journal-title":"SIAM Jour. on Comp."},{"doi-asserted-by":"crossref","unstructured":"A. Ranade, Optimal speedup for backtracking search on a butterfly network, SPAA 1991, 40\u201348.","key":"8_CR12","DOI":"10.1145\/113379.113383"},{"issue":"1","key":"8_CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/0217008","volume":"17","author":"D.M. Nicol","year":"1988","unstructured":"D.M. Nicol, Expected performance of m-solution backtracking, SIAM Journ. on Comp. 17(1), 1988, 114\u2013127.","journal-title":"SIAM Journ. on Comp."},{"doi-asserted-by":"crossref","unstructured":"V. Chvatal, B. Reed, Mick gets some (the odds are on his side), Proc. FOCS 1992.","key":"8_CR14","DOI":"10.1109\/SFCS.1992.267789"},{"key":"8_CR15","first-page":"264","volume":"629","author":"A. Goerdt","year":"1992","unstructured":"A. Goerdt, A threshold for unsatisfiability, Proc. MFCS 1992, LNCS 629, 264\u2013275.","journal-title":"LNCS"},{"unstructured":"R. Matuschka, R. Niedermeier, Verschiedene Heuristiken f\u00fcr die parallele Behandlung des Erf\u00fcllbarkeitsproblems auf dem IPSC, Report of a Fortgeschrittenenpraktikum for Computer Scientists at the Technical University Munich, 1990.","key":"8_CR16"},{"key":"8_CR17","volume-title":"Concrete Mathematics","author":"R.L. Graham","year":"1989","unstructured":"R.L. Graham, D.E. Knuth, O. Patashnik, \u201dConcrete Mathematics\u201d, Addison Wesley, Reading, Massachusetts, 1989."},{"key":"8_CR18","volume-title":"Order statistics","author":"H.A. David","year":"1981","unstructured":"H.A. David, Order statistics, Wiley and Sons Inc., New York, 1981."},{"unstructured":"Greene, D.E. Knuth, Mathematics for the analysis of algorithms, Birkh\u00e4user.","key":"8_CR19"},{"key":"8_CR20","volume-title":"Kendall's advanced theory of statistics, vol. 1","author":"M. Kendall","year":"1987","unstructured":"M. Kendall, A. Stuart, J.K. Ord, Kendall's advanced theory of statistics, vol. 1, Griffin, London, 1987."},{"key":"8_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-99970-3","volume-title":"Analytic inequalities","author":"D.S. Mitrinovic","year":"1970","unstructured":"D.S. Mitrinovic, Analytic inequalities, Springer, Berlin, 1970."},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1214\/aoms\/1177728848","volume":"25","author":"H.O. Hartley","year":"1954","unstructured":"H.O. Hartley, H.A. David, Universal bounds for mean range and extreme observation, Ann. Math. Statist 25, 1954, 84\u201399.","journal-title":"Ann. Math. Statist"},{"unstructured":"I. Alth\u00f6fer, Communication of I. Alth\u00f6fer about a talk of de la Vega.","key":"8_CR23"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049327.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:55:40Z","timestamp":1607550940000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540582770"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0049327","relation":{},"subject":[]}}