Scalable Parallel Algorithms for FPT Problems

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal
dc.contributor.author Shanbhag, Pushkar
dc.contributor.author Symons, Christopher
dc.date.accessioned 2015-12-07T07:56:30Z
dc.date.available 2015-12-07T07:56:30Z
dc.date.copyright 2006
dc.date.issued 2015-12-07
dc.identifier.issn 0178-4617 en_US
dc.identifier.uri http://hdl.handle.net/10725/2769
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.title Scalable Parallel Algorithms for FPT Problems en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Algorithmica en_US
dc.journal.volume 45 en_US
dc.journal.issue 3 en_US
dc.article.pages 269-284 en_US
dc.identifier.doi http://dx.doi.org/10.1007/s00453-006-1214-1 en_US
dc.identifier.ctation Abu-Khzam, F. N., Langston, M. A., Shanbhag, P., & Symons, C. T. (2006). Scalable parallel algorithms for FPT problems. Algorithmica, 45(3), 269-284. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://link.springer.com/article/10.1007/s00453-006-1214-1
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account