Scalable parallel algorithms for dynamic programming on tree decomposition. (c2017)

LAUR Repository

Show simple item record

dc.contributor.author Yassine, Mohamad M.
dc.date.accessioned 2017-12-08T08:16:23Z
dc.date.available 2017-12-08T08:16:23Z
dc.date.copyright 2017 en_US
dc.date.submitted 2017-08-21
dc.identifier.uri http://hdl.handle.net/10725/6738
dc.description.abstract Dynamic programming on tree decompositions is often a key for solving a widerange of optimization problems that would otherwise be intractable. Operations on tree decompositions are amenable to parallelization. However, a systematic approach towards such parallelization is still lacking. In this work, we present a generic and flexible framework for parallel dynamic programming on tree decompositions that can be easily adapted to solve any graph theoretic optimization problem on graphs of bounded treewidth. We show the effectiveness of our framework using the Dominating Set problem as a case study. Our experiments show notable speedups compared to the serial approach. en_US
dc.language.iso en en_US
dc.subject Lebanese American University -- Dissertations en_US
dc.subject Dissertations, Academic en_US
dc.subject Dynamic programming en_US
dc.subject Trees (Graph theory) -- Data processing en_US
dc.subject Parallel algorithms en_US
dc.title Scalable parallel algorithms for dynamic programming on tree decomposition. (c2017) en_US
dc.type Thesis en_US
dc.term.submitted Summer en_US
dc.author.degree MS in Computer Science en_US
dc.author.school SAS en_US
dc.author.idnumber 201003973 en_US
dc.author.commembers Haraty, Ramzi
dc.author.commembers Issa, Leila
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.description.physdesc 1 hard copy: ix, 49 leaves; 30 cm. available at RNL. en_US
dc.author.advisor Abu-Khzam, Faisal
dc.keywords Parallel Processing en_US
dc.keywords Tree Decomposition en_US
dc.keywords Treewidth en_US
dc.keywords Dynamic Programming en_US
dc.keywords Dominating Set en_US
dc.description.bibliographiccitations Bibliography : leaves 47-49. en_US
dc.identifier.doi https://doi.org/10.26756/th.2017.32 en_US
dc.author.email mohamad.yassine@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php en_US
dc.publisher.institution Lebanese American University en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account