%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft24
%@issn 0304-3975
%@usergroup administrator
%@usergroup simone
%3 parallel.pdf
%2 sid.inpe.br/mtc-m18@80/2008/11.20.18.45.19
%4 sid.inpe.br/mtc-m18@80/2008/11.20.18.45
%X Three new parallel scalable algorithms for solving the Subset-Sum Problem in  time and O(n+c) space in the PRAM model are presented, where n is the number of objects, c is the capacity, wmin is the smallest weight and p is the number of processors. These time and space bounds are better than the direct parallelization of Bellmans algorithm, which was the most efficient known result.
%8 Nov.
%N 1/3
%T Parallel time and space upper-bounds for the subset-sum problem
%@secondarytype PRE PI
%K Subset-sum problem, Knapsack problem, Parallel algorithms, Dynamic programming, Upper-bound complexity.
%@group
%@group
%@group LAC-CTE-INPE-MCT-BR
%@secondarykey INPE--PRE/
%@affiliation ITA
%@affiliation ITA
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B Theoretical Computer Science
%P 342-348
%D 2008
%V 407
%@doi 10.1016/j.tcs.2008.06.051
%A Sanches, C. A. A.,
%A Soma, N. Y.,
%A Yanasse, Horácio Hideki,
%@dissemination PORTALCAPES
%@area COMP