×

On importance of a special sorting in the maximum-weight clique algorithm based on colour classes. (English) Zbl 1160.90707

Le Thi, Hoai An (ed.) et al., Modelling, computation and optimization in information systems and management sciences. Second international conference MCO 2008, Metz, France - Luxembourg, September 8–10, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87476-8/pbk). Communications in Computer and Information Science 14, 165-174 (2008).
Summary: A new sorting strategy is proposed to be used in the maximum weight clique finding algorithm, which is known to be the fastest at the moment. It is based on colour classes, i.e. on heuristic colouring that is used to prune efficiently branches by excluding from the calculation formulae vertices of the same colours. That is why the right ordering before colouring is so crucial before executing the heuristic colouring and consequently the main maximum weight clique searching routine. Computational experiments with random graphs were conducted and have shown a sufficient increase of performance considering the type of application dealt with in the article.
For the entire collection see [Zbl 1149.90004].

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] MacWilliams, J., Sloane, N.J.A.: The theory of error correcting codes. North-Holland, Amsterdam (1979) · Zbl 0447.94016
[2] Corradi, K., Szabo, S.: A combinatorial approach for Keller’s Conjecture. Periodica Mathematica Hungarica 21, 95–100 (1990) · Zbl 0718.52017 · doi:10.1007/BF01946848
[3] Berman, P., Pelc, A.: Distributed fault diagnosis for multiprocessor systems. In: 20th Annual International Symposium on Fault-Tolerant Computing, Newcastle, UK, pp. 340–346 (1990)
[4] Horaud, R., Skordas, T.: Stereo correspondence through feature grouping and maximal cliques. IEEE Transactions on Pattern Analysis and Machine Intelligence 11, 1168–1180 (1989) · Zbl 05112686 · doi:10.1109/34.42855
[5] Mitchell, E.M., Artymiuk, P.J., Rice, D.W., Willet, P.: Use of techniques derived from graph theory to compare secondary structure motifs in proteins. Journal of Molecular Biology 212, 151–166 (1989) · doi:10.1016/0022-2836(90)90312-A
[6] Jansen, K., Scheffler, P., Woeginger, G.: The disjoint cliques problem. Operations Research 31, 45–66 (1997) · Zbl 0881.90123 · doi:10.1051/ro/1997310100451
[7] Bomze, M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization 4. Kluwer Academic Publishers, Boston (1999) · Zbl 1253.90188
[8] Carraghan, R., Pardalos, P.M.: A parallel algorithm for the maximum weight clique problem. Technical report CS-90-40, Dept of Computer Science, Pennsylvania State University (1990) · Zbl 0711.90080
[9] Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Op. Research Letters 9, 375–382 (1990) · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C
[10] Ostergard, P.R.J.: A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing 8, 424–436 (2001)
[11] Johnson, D.S., Trick, M.A. (eds.): Cliques, Colouring and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society (1996)
[12] Kumlander, D.: Some practical algorithms to solve the maximum clique problem. Tallinn University of Technology Press, Tallinn (2005) · Zbl 1079.68076
[13] Kumlander, D.: Network resources for the maximum clique problem, http://www.kumlander.eu/graph · Zbl 1157.68406
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.