Abstract
Given a connected, undirected graph G = (V,E), where V is the set of vertices and E is the set of edges, the clique partitioning problem (CPP) seeks on this graph a partition of set V into minimum number of subsets such that each subset is a clique. The CPP is an \(\mathcal {NP}\)-Hard problem and finds numerous practical applications in diverse domains like digital design synthesis, clustering etc. Despite its computational complexity and its numerous applications, only problem-specific heuristics have been developed so far for this problem in the literature. In this paper, two metaheuristic techniques – a steady-state grouping genetic algorithm and an artificial bee colony algorithm – are proposed for the CPP. Both the proposed approaches are designed in such a way that the grouping structure of the CPP is exploited effectively while generating new solutions. Since artificial bee colony algorithm is comparatively a new metaheuristic technique, special attention has been given to the design of this algorithm for the CPP and we came out with a new neighboring solution generation method utilizing solution components from multiple solutions. The proposed approaches have been tested on publicly available 37 DIMACS graph instances. Computational results show the effectiveness of the proposed approaches.
Similar content being viewed by others
References
Bhasker J, Samad T (1991) The clique partitioning problem. Comput Math Appl 22:1–11
Dao TK, Pan TS, Nguyen TT, Chu SC (2015) A compact articial bee colony optimization for topology control scheme in wireless sensor networks. J Inf Hiding Multimed Signal Process 6:297–310
Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York
Falkenauer E (1998) Genetic algorithms and grouping problems. John Wiley & Sons, Chicester
Gao W, Liu S (2011) Improved artificial bee colony algorithm for global optimization. Inf Process Lett 111:871–882
Garey MR, Johnson DS (1979) Computers and Intractibility: A Guide to the Theory of NP-completeness. Freeman and Co., San Francisco
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press
Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Computer Engineering Department Engineering Faculty. Erciyes University, Turkey
Karp RM (1972) Reducibility among combinatorial problems. In: Miller R. E., Thatcher J. W. (eds) Complexity of Computer Computations New York: Plenum, pp 85–103
Kim JT, Shin DR (2002) New efficient clique partitioning algorithms for register-transfer synthesis of data paths. J Korean Phys Soc 40:754–758
Pan QK, Tasgetiren MF, Suganthan PN, Chua TJ (2011) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci 181:2455–2468
Pandiri V, Singh A (2016) Swarm intelligence approaches for multidepot salesmen problems with load balancing. Appl Intell 44:849–861
Singh A (2009) An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl Soft Comput 9:625–631
Sundar S, Singh A (2010a) A swarm intelligence approach to the quadratic minimum spanning tree problem. Inf Sci 180:3182–3191
Sundar S, Singh A (2010b) A swarm intelligence approach to the quadratic multiple knapsack problem ICONIP 2010, Part I, Lecture Notes in Computer Science, vol 6443. Springer, pp 626–633
Tseng CJ (1984) Automated synthesis of data paths in digital systems. Ph. D. Thesis, Dept. of Electrical and Computer Engineering Carnegie-Mellon University, Pittsburg, PA
Wang H, Wu Z, Rahnamayan S, Sun H, Liu Y, Pan JS (2014) Multi-strategy ensemble artificial bee colony algorithm. Inf Sci 279:587–603
Zhao J, Lv L, Wang H, Tan DK, Ye J, Sun H, Hu YT (2016) Artifcial bee colony based on special central and adapt number of dimensions learning. J Inf Hiding Multimed Signal Process 7:645–652
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sundar, S., Singh, A. Two grouping-based metaheuristics for clique partitioning problem. Appl Intell 47, 430–442 (2017). https://doi.org/10.1007/s10489-017-0904-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-017-0904-5