عرض بسيط للتسجيلة

المرشدJaoua, Ali
المؤلفSafi, Zeineb
تاريخ الإتاحة2017-11-22T11:21:29Z
تاريخ النشر2017-06
المعرّفORCID ID: http://orcid.org/0000-0003-0526-8949
معرّف المصادر الموحدhttp://hdl.handle.net/10576/5794
الملخصThe 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.
راعي المشروعNPRP grant #06-1220-1-233 from the Qatar National Research Fund (a member of Qatar Foundation).
اللغةen
الموضوعformal concept analysis
maximum cliques
Computer science
العنوانA conceptual heuristic for solving the maximum clique problem
النوعMaster Thesis
التخصصComputing
dc.accessType Open Access


الملفات في هذه التسجيلة

Thumbnail

هذه التسجيلة تظهر في المجموعات التالية

عرض بسيط للتسجيلة