{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T05:27:32Z","timestamp":1675229252456},"publisher-location":"Berlin, Heidelberg","reference-count":30,"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\/bfb0027119","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"87-114","source":"Crossref","is-referenced-by-count":3,"title":["An introduction to parallel dynamic programming"],"prefix":"10.1007","author":[{"given":"Marc","family":"Gengler","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"5_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley, Reading (MA), USA, 1974."},{"key":"5_CR2","volume-title":"Dynamic Programming","author":"R. E. Bellman","year":"1957","unstructured":"R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, USA, 1957."},{"key":"5_CR3","doi-asserted-by":"crossref","volume-title":"Applied Dynamic Programming","author":"R. E. Bellman","year":"1962","unstructured":"R. E. Bellman and S. E. Dreyfus. Applied Dynamic Programming. Princeton University Press, Princeton, USA, 1962.","DOI":"10.1515\/9781400874651"},{"key":"5_CR4","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1109\/PGEC.1966.264565","volume":"15","author":"A. J. Bernstein","year":"1966","unstructured":"A. J. Bernstein. Analysis of Programs for Parallel Processing. IEEE Transactions on Electronic Computers, 15:757\u2013762, 1966.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1:269\u2013271, 1959.","journal-title":"Numer. Math."},{"key":"5_CR6","volume-title":"Mathematics in Science and Engeneering, Volume 130","author":"S. E. Dreyfus","year":"1977","unstructured":"S. E. Dreyfus and A. M. Law. The Art and Theory of Dynamic Programming. Mathematics in Science and Engeneering, Volume 130. Academic Press, New York, USA, 1977."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in Random Access Machines. In Proceedings of STOC-10, pages 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"key":"5_CR8","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, USA, 1979."},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Z. Ghalil and K. Park. Dynamic Programming with Convexity, Concavity and Sparsity. Theoretical Computer Science, pages 49\u201376, 1992.","DOI":"10.1016\/0304-3975(92)90135-3"},{"key":"5_CR10","unstructured":"L. J. Guibas, H. T. Kung, and C. D. Thompson. Direct VLSI Implementation of Combinatorial Algorithms. In Proc. Conf. on Very Large Scale Integration, pages 509\u2013525, 1979."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among Combinatorial Problems. In J. W. Thatcher R. E. Miller, editor, Complexity of Computer Computations, pages 85\u2013103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"5_CR12","volume-title":"Parallel Computing","author":"V. Kumar","year":"1994","unstructured":"V. Kumar, Grama A., A. Gupta, and G. Karypis. Parallel Computing. Benjamin Cummings, Redwood City (CA), USA, 1994."},{"key":"5_CR13","volume-title":"Search in Artificial Intelligence","author":"V. Kumar","year":"1988","unstructured":"V. Kumar and L. Kanal. The CDP: A Unifying Formulation for Heuristic Search, Dynamic Programming and Branch-and-Bound. In Search in Artificial Intelligence, Berlin, D, 1988. Springer Verlag."},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner. The Circuit Value Problem is Log-space Complete for P. SIGACT News 7, 1:18\u201320, 1975.","journal-title":"SIGACT News"},{"key":"5_CR15","volume-title":"Principles of Dynamic Programming, Volume 1","author":"R. E. Larson","year":"1978","unstructured":"R. E. Larson and J. L. Casti. Principles of Dynamic Programming, Volume 1. Marcel Dekker, New York, USA, 1978."},{"key":"5_CR16","volume-title":"Principles of Dynamic Programming, Volume 2","author":"R. E. Larson","year":"1982","unstructured":"R. E. Larson and J. L. Casti. Principles of Dynamic Programming, Volume 2. Marcel Dekker, New York, USA, 1982."},{"key":"5_CR17","unstructured":"G. J. Li and B. W. Wah. Parallel Processing of Serial Dynamic Programming Problems. In Proceedings COMPSAC 85, pages 81\u201389, 1985."},{"key":"5_CR18","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 and Sons, Chichester, UK, 1990."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"G. L. Miller, V. Ramanchandran, and E. Kaltofen. Efficient Parallel Evaluation of Straight-line Code and Arithmetic Circuits. In Aegean Workshop on Computing VLSI Algorithms and Architectures, ACM EATCS, 1986.","DOI":"10.1007\/3-540-16766-8_21"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"G. L. Miller and S.-H. Teng. Dynamic Parallel Complexity of Computational Circuits. In Proceedings of STOC, pages 254\u2013263, 1987.","DOI":"10.1145\/28395.28423"},{"key":"5_CR21","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. Operations Research, 18:24\u201334, 1970.","journal-title":"Operations Research"},{"key":"5_CR22","volume-title":"Theory of Linear and Integer Programming","author":"S. Schrijver","year":"1984","unstructured":"S. Schrijver. Theory of Linear and Integer Programming. Wiley and Sons, Chichester, UK, 1984."},{"key":"5_CR23","volume-title":"Algorithms","author":"R. Sedgewick","year":"1983","unstructured":"R. Sedgewick. Algorithms. Addison Wesley, Reading (MA), USA, 1983."},{"key":"5_CR24","volume-title":"Mathematics and its Applications","author":"D. K. Smith","year":"1991","unstructured":"D. K. Smith. Dynamic Programming: a Practical Introduction. Mathematics and its Applications. Ellis Horwood, Chichester, UK, 1991."},{"key":"5_CR25","volume-title":"Dynamic Programming","author":"M. Sniedovich","year":"1992","unstructured":"M. Sniedovich. Dynamic Programming. Marcel Dekker, New York, USA, 1992."},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0202004","volume":"2","author":"P. M. Spira","year":"1973","unstructured":"P. M. Spira. A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time O(N\n2 log2\nN). SIAM J. Comput., 2:28\u201332, 1973.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"5_CR27","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1016\/0743-7315(90)90139-G","volume":"8","author":"S.-H. Teng","year":"1990","unstructured":"S.-H. Teng. Adaptive Parallel Algorithms for Integral Knapsack Problems. J. of Parallel and Distributed Computing, 8(4):400\u2013406, 1990.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. G. Valiant","year":"1983","unstructured":"L. G. Valiant, S. Skyum, and S. Berkowitz. Fast Parallel Computation of Polynomials using few Processors. SIAM J. Comput, 12:641\u2013644, 1983.","journal-title":"SIAM J. Comput"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/321765.321769","volume":"20","author":"T. A. Williams","year":"1973","unstructured":"T. A. Williams and G. P. White. A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in N-Node Nonnegative-Distance Networks. J. of the ACM, 20:389\u2013390, 1973.","journal-title":"J. of the ACM"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1145\/321707.321712","volume":"19","author":"J. Y. Yen","year":"1972","unstructured":"J. Y. Yen. Finding the Lengths of All Shortest Paths in N-Node Nonnegative-Distance Complete Networks Using N\n3\/2 Additions and N\n3 Comparisons. J. of the ACM, 19:423\u2013424, 1972.","journal-title":"J. of the ACM"}],"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\/BFb0027119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,5]],"date-time":"2019-02-05T02:05:46Z","timestamp":1549332346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":30,"URL":"http:\/\/dx.doi.org\/10.1007\/bfb0027119","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1996]]}}}