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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2006
|
| Online Access: | 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |