Alternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems.

Mochamad Suyudi, Asep K Supriatna, Sukono Sukono

Abstract


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.


Keywords


Maximum clique problem, Branch and Bound algorithm, color class, k-clique covering vertex set.

Full Text:

PDF

References


Aslan, Murat., and Baykan, Nurdan. Akhan., (2016). A Performance Comparison of Graph Coloring Algorithms, International Conference on Advanced Technology and Science. 266-273

Babel, L., and Tinhofer, G., (1990). A Branch and Bound for the Maximum Clique Problem, Methods and Models of Operations Research. 34(3), 207-217.

Balasundaram, B., Butenko, S., and Hicks, I. V. (2011). Clique Relaxation in Social Network Analysis: The Maximum k-plex Problem. 59(1), 133-142.

Boginski, V., Butenko, S., and Pardalos, P. M. (2006). Mining Market Data: A Network Approach. 33(11), 3171-3184.

Butenko, S., and Wilhelm, W. E. (2005). Clique-detection Models in Computational Biochemistry and Genomics. Europan Journal of Operation Research, 173(2006), 1-17.

Pardalos, P. M., and Xue, J. (1994). The Maximum Clique Problem. Journal of Global Optimization, 4(3), 301-328.

Ravetti, M. G., and Moscato, P. (2008). Identi_cation of a 5-protein Biomarker Molecular Signature for Predictiong Alzheimer's Disease. PLoS One, 3(9), 1-12.

Suyudi, M., Mohd, I. B., Mamat, M., Sopiyan, S., and Supriatna, A. K. (2014). Solution of Maximum Clique Problem by Using Branch and Bound Method. 8(2), 81-90.

Szabo, S., and Zavalnij, B. (2018). Decomposing Clique Search Problems into Smaller Instances Based on Node and Edge Colorings. Discrete Applied Mathematics, 242(2018), 118-129.

Wu, Q., and Hao, J.-K. (2014). A Review on Algorithms for Maximum Clique Problem. European Journal of Operational Research, 242(2015), 693-709.




DOI: https://doi.org/10.46336/ijqrm.v1i4.82

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Mochamad Suyudi, Asep K Supriatna, Sukono Sukono

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Published By: 

IJQRM: Jalan Riung Ampuh No. 3, Riung Bandung, Kota Bandung 40295, Jawa Barat, Indonesia

 

IJQRM Indexed By: 

width= width= width= width= width= width= 

 


Lisensi Creative Commons Creation is distributed below Lisensi Creative Commons Atribusi 4.0 Internasional.


View My Stats