Maximal clique enumeration. (c2007)
Includes bibliographical references (leave 34).
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/1005 https://doi.org/10.26756/th.2007.51 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513455710535680 |
|---|---|
| author | Barghout, Hamed |
| author_facet | Barghout, Hamed |
| author_role | author |
| dc.creator.none.fl_str_mv | Barghout, Hamed |
| dc.date.none.fl_str_mv | 2007 2007-02-22 2011-11-17T13:04:13Z 2011-11-17T13:04:13Z 2011-11-17 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/1005 https://doi.org/10.26756/th.2007.51 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Lebanese American University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Graph theory |
| dc.title.none.fl_str_mv | Maximal clique enumeration. (c2007) |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | Includes bibliographical references (leave 34). |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_d4764f7d1a663f622a46244fc737cdff |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/1005 |
| publishDate | 2007 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Maximal clique enumeration. (c2007)Barghout, HamedGraph theoryIncludes bibliographical references (leave 34).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.1 bound copy: 34 leaves; charts; 31 cm. Available at RNL.Lebanese American University2011-11-17T13:04:13Z2011-11-17T13:04:13Z20072011-11-172007-02-22Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/1005https://doi.org/10.26756/th.2007.51eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/10052020-05-18T14:53:53Z |
| spellingShingle | Maximal clique enumeration. (c2007) Barghout, Hamed Graph theory |
| status_str | publishedVersion |
| title | Maximal clique enumeration. (c2007) |
| title_full | Maximal clique enumeration. (c2007) |
| title_fullStr | Maximal clique enumeration. (c2007) |
| title_full_unstemmed | Maximal clique enumeration. (c2007) |
| title_short | Maximal clique enumeration. (c2007) |
| title_sort | Maximal clique enumeration. (c2007) |
| topic | Graph theory |
| url | http://hdl.handle.net/10725/1005 https://doi.org/10.26756/th.2007.51 |