Maximal clique enumeration. (c2007)

LAUR Repository

Show simple item record

dc.contributor.author Barghout, Hamed
dc.date.accessioned 2011-11-17T13:04:13Z
dc.date.available 2011-11-17T13:04:13Z
dc.date.copyright 2007 en_US
dc.date.issued 2011-11-17
dc.date.submitted 2007-02-22
dc.identifier.uri http://hdl.handle.net/10725/1005
dc.description Includes bibliographical references (leave 34). en_US
dc.description.abstract Maximal clique enumeration is one of the most important tools for solving problems in a wide variety of application domains. Classical enumeration techniques suffer from being too slow on large scale data. New techniques, introduced in the work of Abu-Khzam, decompose the input graph into a smaller subgraph and its complement in an attempt to reduce the search space and confine the exponential-time enumeration to subgraphs that are often small in practice. Such subgraphs are called dominating structures in our work. We discuss different dominating structures for the maximal clique enumeration problem, but we focus in our implementations on two of them. The first structure is a vertex cover of the input graph and the second one is a maximal matching of the complement of the graph. We consider these two edge capturing structures on graphs of different densities. Our experimental study revealed that the vertex cover approach is faster than the well-known Bron and Kerbosch (BK) algorithm on sparse graphs, as well as graphs whose vertex covers are small. Theoretical analysis supports our findings since the run time is improved from O(3n/3 ) to O(3k/3 ) , where k is the vertex cover size. Moreover, our second approach proved to be faster than BK on graphs of high density. en_US
dc.language.iso en en_US
dc.subject Graph theory en_US
dc.title Maximal clique enumeration. (c2007) en_US
dc.type Thesis en_US
dc.term.submitted Fall en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200101037 en_US
dc.author.commembers Dr. Nashat Mansour
dc.author.commembers Dr. Haidar Harmanani
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: 34 leaves; charts; 31 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.2007.51 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