A decentralized load balancing strategy for parallel search-three optimization. (c2010)

LAUR Repository

Show simple item record

dc.contributor.author Mouawad, Amer E.
dc.date.accessioned 2011-11-29T12:26:02Z
dc.date.available 2011-11-29T12:26:02Z
dc.date.copyright 2010 en_US
dc.date.issued 2011-11-29
dc.date.submitted 2011-06
dc.identifier.uri http://hdl.handle.net/10725/1034
dc.description Includes bibliographical references (leaves 28-31). en_US
dc.description.abstract Current generation supercomputers have thousands of cores awaiting highly demanding computations and applications. One area that could largely benefit from such processing capabilities is clearly that of exact algorithms for NP-hard problems. The interest in exact algorithms is more than fifty years old, but seems to have gained great momentum recently with the emergence of parameterized complexity and new exact algorithmic techniques. Moreover, given the proved limitation of polynomial-time approximation algorithms, many research fields witness greater need for accurate computations. Motivated by the above facts, we propose a general implementation framework that targets parallel exact algorithms for NP-hard graph problems. In addition to efficiency, we tackle the problem of scalability by combining a decentralized dynamic load balancing strategy with new coding techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the Vertex Cover and Dominating Set problems. We present experimental results that show notable improved running times and high scalability on all types of input instances. en_US
dc.language.iso en en_US
dc.subject Parallel processing (Electronic computers) en_US
dc.subject Trees (Graph theory) -- Data processing en_US
dc.subject Computer algorithms en_US
dc.title A decentralized load balancing strategy for parallel search-three optimization. (c2010) en_US
dc.type Thesis en_US
dc.term.submitted Spring en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200400377 en_US
dc.author.commembers Dr. Samer Haber
dc.author.commembers Dr. Ramzi Haraty
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: x, 31 leaves; ill.; 31 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Faisal Abu-Khzam
dc.keywords Parallel Algorithms en_US
dc.keywords Exact Algorithms en_US
dc.keywords Vertex Cover en_US
dc.keywords Dominating Set en_US
dc.keywords Dynamic Load Balancing en_US
dc.keywords Recursive Backtracking en_US
dc.identifier.doi https://doi.org/10.26756/th.2010.54 en_US
dc.publisher.institution 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