Scalable Parallel Algorithms for FPT Problems
Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are comput...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , |
| التنسيق: | article |
| منشور في: |
2006
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/2769 http://dx.doi.org/10.1007/s00453-006-1214-1 http://link.springer.com/article/10.1007/s00453-006-1214-1 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513459361677312 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Langston, Micheal Shanbhag, Pushkar Symons, Christopher |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Langston, Micheal Shanbhag, Pushkar Symons, Christopher |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Langston, Micheal Shanbhag, Pushkar Symons, Christopher |
| dc.date.none.fl_str_mv | 2006 2015-12-07T07:56:30Z 2015-12-07T07:56:30Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 0178-4617 http://hdl.handle.net/10725/2769 http://dx.doi.org/10.1007/s00453-006-1214-1 Abu-Khzam, F. N., Langston, M. A., Shanbhag, P., & Symons, C. T. (2006). Scalable parallel algorithms for FPT problems. Algorithmica, 45(3), 269-284. http://link.springer.com/article/10.1007/s00453-006-1214-1 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Algorithmica |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Scalable Parallel Algorithms for FPT Problems |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and various forms of parallel algorithms are devised, implemented, and compared. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. Target problems need only be amenable to reduction and decomposition. Applications in high throughput computational biology are also discussed. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_3260b0101faeca561fcd6ab6d218432e |
| identifier_str_mv | 0178-4617 Abu-Khzam, F. N., Langston, M. A., Shanbhag, P., & Symons, C. T. (2006). Scalable parallel algorithms for FPT problems. Algorithmica, 45(3), 269-284. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/2769 |
| publishDate | 2006 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Scalable Parallel Algorithms for FPT ProblemsAbu-Khzam, Faisal N.Langston, MichealShanbhag, PushkarSymons, ChristopherAlgorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and various forms of parallel algorithms are devised, implemented, and compared. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. Target problems need only be amenable to reduction and decomposition. Applications in high throughput computational biology are also discussed.PublishedN/A2015-12-07T07:56:30Z2015-12-07T07:56:30Z20062015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0178-4617http://hdl.handle.net/10725/2769http://dx.doi.org/10.1007/s00453-006-1214-1Abu-Khzam, F. N., Langston, M. A., Shanbhag, P., & Symons, C. T. (2006). Scalable parallel algorithms for FPT problems. Algorithmica, 45(3), 269-284.http://link.springer.com/article/10.1007/s00453-006-1214-1enAlgorithmicainfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27692020-05-25T08:10:07Z |
| spellingShingle | Scalable Parallel Algorithms for FPT Problems Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Scalable Parallel Algorithms for FPT Problems |
| title_full | Scalable Parallel Algorithms for FPT Problems |
| title_fullStr | Scalable Parallel Algorithms for FPT Problems |
| title_full_unstemmed | Scalable Parallel Algorithms for FPT Problems |
| title_short | Scalable Parallel Algorithms for FPT Problems |
| title_sort | Scalable Parallel Algorithms for FPT Problems |
| url | http://hdl.handle.net/10725/2769 http://dx.doi.org/10.1007/s00453-006-1214-1 http://link.springer.com/article/10.1007/s00453-006-1214-1 |