A local core number based algorithm for the maximum clique problem

سال انتشار: 1400
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 233

فایل این مقاله در 15 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_COMB-10-3_002

تاریخ نمایه سازی: 17 خرداد 1400

چکیده مقاله:

‎The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph‎. ‎MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications‎. ‎In this paper‎, ‎we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph‎. ‎Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but‎, ‎as a new pruning strategy‎, ‎we show that local core number is more efficient‎. ‎Moreover‎, ‎instead of neighbors set of a vertex‎, ‎our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process‎. ‎This subset is based on the core of the vertices of a given graph‎. ‎We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction‎. ‎Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs‎.

نویسندگان

Neda Mohammadi

Department of computer science, University of Shahrekord, Shahrekord, Iran

Mehdi Kadivar

Department of computer science, University of Shahrekord, Shahrekord, Iran