Show simple item record

AdvisorJaoua, Ali
AuthorSafi, Zeineb
Available date2017-11-22T11:21:29Z
Publication Date2017-06
IdentifierORCID ID: http://orcid.org/0000-0003-0526-8949
URIhttp://hdl.handle.net/10576/5794
AbstractThe maximum clique problem (MCP) is the problem of finding the clique with maximum cardinality in a graph. It has been intensively studied for years by computer scientists and mathematicians. It has many practical applications and it is usually the computational bottleneck. Due to the complexity of the problem, exact solutions can be very computationally expensive. In the scope of this thesis, a polynomial time heuristic that is based on Formal Concept Analysis has been developed. The developed approach has three variations that use different algorithm design approaches to solve the problem, a greedy algorithm, a backtracking algorithm and a branch and bound algorithm. The parameters of the branch and bound algorithm are tuned in a training phase and the tuned parameters are tested on the BHOSLIB benchmark graphs. The developed approach is tested on all the instances of the DIMACS benchmark graphs, and the results show that the maximum clique is obtained for 70% of the graph instances. The developed approach is compared to several of the most effective recent algorithms.
SponsorNPRP grant #06-1220-1-233 from the Qatar National Research Fund (a member of Qatar Foundation).
Languageen
Subjectformal concept analysis
maximum cliques
Computer science
TitleA conceptual heuristic for solving the maximum clique problem
TypeMaster Thesis
DepartmentComputing
dc.accessType Open Access


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record