Fixed-parameter algorithms for hitting set problems. (c2006)

LAUR Repository

Show simple item record

dc.contributor.author Masri, Rola El.
dc.date.accessioned 2011-09-27T06:10:40Z
dc.date.available 2011-09-27T06:10:40Z
dc.date.copyright 2006 en_US
dc.date.issued 2011-09-27
dc.date.submitted 2006-06-16
dc.identifier.uri http://hdl.handle.net/10725/633
dc.description Includes bibliographical references (leaves 56-57). en_US
dc.description.abstract The Hitting Set problem received a great deal of attention lately due to its plethora of applications in scientific domains. Many Algorithms have been developed to solve this problem by targeting the reduction of the worst-case run time. The most recent proposed algorithm employs a technique called pseudo-kernelization, introduced by F. Abu Khzam. Pseudo-kernelization seeks to find favorable conditions whose presence leads to a faster search strategy, and whose absence leads to a better reduction of the problem instance. When applied to the 3-Hitting Set problem, it provides a great improvement over the previously known algorithms. In this paper, we consider the algorithm ofH. Fernau, which has the best worst-case run time. We show that combining the methods used in Fernau's algorithm and the pseudokernelization technique gives the best run times for 3-Hitting Set. We provide empirical evidence that supports this claim. Moreover, we show how applying pseudo-kernelization to the general d-Hitting Set problem provides an improvement over the previously developed algorithms. en_US
dc.language.iso en en_US
dc.subject Algorithms en_US
dc.subject Parameter estimation en_US
dc.title Fixed-parameter algorithms for hitting set problems. (c2006) 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 199308260 en_US
dc.author.commembers Dr. Nashaat Mansour
dc.author.commembers Dr. May Hamdan
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: x, 75 leaves; ill.; 30 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Faisal N. Abu Khzam
dc.identifier.doi https://doi.org/10.26756/th.2006.28 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