Improved search-tree algorithms for the cluster edit problem. (c2011)
Includes bibliographical references (leaves 25-26).
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/997 https://doi.org/10.26756/th.2011.22 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513455701098496 |
|---|---|
| author | Ghrayeb, Ali Kassem |
| author_facet | Ghrayeb, Ali Kassem |
| author_role | author |
| dc.creator.none.fl_str_mv | Ghrayeb, Ali Kassem |
| dc.date.none.fl_str_mv | 2011-11-17T09:33:03Z 2011-11-17T09:33:03Z 2011 2011-11-17 2011-05-30 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/997 https://doi.org/10.26756/th.2011.22 |
| 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 | Pattern recognition systems Mathematics -- Data processing Artificial intelligence |
| dc.title.none.fl_str_mv | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | Includes bibliographical references (leaves 25-26). |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_e0e5aed93d28253f51acd2f8e451fc39 |
| 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/997 |
| publishDate | 2011 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Improved search-tree algorithms for the cluster edit problem. (c2011)Ghrayeb, Ali KassemPattern recognition systemsMathematics -- Data processingArtificial intelligenceIncludes bibliographical references (leaves 25-26).In the Cluster Edit problem, we are asked to transform a given graph into a transitive graph, via edge deletion or addition operations, to make sure that the vertices are partitioned into a disjoint union of cliques. Cluster Edit finds application in a number of domains, including computational biology and social networks. When parameterized by the number of permitted edge-edit operation (k), the problem can be solved in O (3k) time via a search-tree backtracking strategy. The current fastest worstcase fixed-parameter algorithm described in [7] adopts the same strategy and solves Cluster Edit in O (1.82k). This thesis presents new techniques to enhance any search tree- based algorithm for the Cluster Edit problem. These techniques, which include new heuristics and impose bounds on allowable edge operations per vertex, cause effective pruning of search-trees and yield noticeable improvements in experimental running times on almost all types of input instances.1 bound copy: x, 26 leaves; 30 cm. available at RNL.Lebanese American University2011-11-17T09:33:03Z2011-11-17T09:33:03Z20112011-11-172011-05-30Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/997https://doi.org/10.26756/th.2011.22eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/9972020-05-18T14:53:53Z |
| spellingShingle | Improved search-tree algorithms for the cluster edit problem. (c2011) Ghrayeb, Ali Kassem Pattern recognition systems Mathematics -- Data processing Artificial intelligence |
| status_str | publishedVersion |
| title | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| title_full | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| title_fullStr | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| title_full_unstemmed | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| title_short | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| title_sort | Improved search-tree algorithms for the cluster edit problem. (c2011) |
| topic | Pattern recognition systems Mathematics -- Data processing Artificial intelligence |
| url | http://hdl.handle.net/10725/997 https://doi.org/10.26756/th.2011.22 |