Open AccessAlternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems.
Author(s) -
Muhammad Suyudi,
Asep K. Supriatna,
Sukono Sukono
Publication year - 2020
Publication title -
international journal of quantitative research and modeling
Language(s) - English
Resource type - Journals
eISSN - 2722-5046
pISSN - 2721-477X
DOI - 10.46336/ijqrm.v1i4.82
Subject(s) - combinatorics , vertex (graph theory) , clique graph , mathematics , cardinality (data modeling) , independent set , branch and bound , split graph , upper and lower bounds , simplex graph , clique , clique problem , discrete mathematics , graph , algorithm , chordal graph , computer science , graph power , 1 planar graph , line graph , mathematical analysis , data mining
The Maximum clique problem (MCP) is graph theory problem that demand complete subgraf with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm, in this paper we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarenteed finnding maximum clique.