| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16c.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 8JMKD3MGP8W/3498HKL |
| Repository | sid.inpe.br/mtc-m18@80/2008/11.20.18.45 (restricted access) |
| Last Update | 2008:11.20.18.45.18 (UTC) administrator |
| Metadata Repository | sid.inpe.br/mtc-m18@80/2008/11.20.18.45.19 |
| Metadata Last Update | 2018:06.04.04.05.46 (UTC) administrator |
| Secondary Key | INPE--PRE/ |
| DOI | 10.1016/j.tcs.2008.06.051 |
| ISSN | 0304-3975 |
| Citation Key | SanchesSomaYana:2008:PaTiSp |
| Title | Parallel time and space upper-bounds for the subset-sum problem  |
| Year | 2008 |
| Month | Nov. |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 431 KiB |
| 2. Context | |
| Author | 1 Sanches, C. A. A. 2 Soma, N. Y. 3 Yanasse, Horácio Hideki |
| Group | 1 2 3 LAC-CTE-INPE-MCT-BR |
| Affiliation | 1 ITA 2 ITA 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Journal | Theoretical Computer Science |
| Volume | 407 |
| Number | 1/3 |
| Pages | 342-348 |
| History (UTC) | 2008-11-20 18:45:20 :: simone -> administrator :: 2018-06-04 04:05:46 :: administrator -> marciana :: 2008 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Keywords | Subset-sum problem Knapsack problem Parallel algorithms Dynamic programming Upper-bound complexity |
| Abstract | 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. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > Parallel time and... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | parallel.pdf |
| User Group | administrator simone |
| Visibility | shown |
| Archiving Policy | denypublisher denyfinaldraft24 |
| Read Permission | deny from all and allow from 150.163 |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | PORTALCAPES |
| Host Collection | sid.inpe.br/mtc-m18@80/2008/03.17.15.17 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel documentstage e-mailaddress electronicmailaddress format isbn label lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress project readergroup resumeid rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url versiontype |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |