A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

References

• Akutsu T, Hayashida M, Tomita E, Suzuki J (2004) Protein threading with profiles and constraints. Proc. 4th IEEE Sympos. Bioinformatics Bioengrg. (IEEE Computer Society, Washington, DC), 537–544.Google Scholar
• Alidaee B, Glover F, Kochenberger G, Wang H (2007) Solving the maximum edge weight clique problem via unconstrained quadratic programming. Eur. J. Oper. Res. 181(2):592–597.Crossref, Google Scholar
• Amin AT, Hakimi SL (1972) Upper bounds on the order of a clique of a graph. SIAM J. Appl. Math. 22(4):569–573.Crossref, Google Scholar
• Aringhieri R, Cordone R (2011) Comparing local search metaheuristics for the maximum diversity problem. J. Oper. Res. Soc. 62(2):266–280.Crossref, Google Scholar
• Batsyn M, Goldengorin B, Maslov E, Pardalos PM (2014) Improvements to MCS algorithm for the maximum clique problem. J. Combin. Optim. 27(2):397–416.Crossref, Google Scholar
• Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Kluwer Academic Publishers, Dordrecht, Netherlands), 1–74.Crossref, Google Scholar
• Brown JB, Bahadur D, Tomita E, Akutsu T (2006) Multiple methods for protein side chain packing using maximum weight cliques. Genome Informatics 17(1):3–12.Google Scholar
• Budinich M (2003) Exact bounds on the order of the maximum clique of a graph. Discrete Appl. Math. 127(3):535–543.Crossref, Google Scholar
• Bulò SR, Pelillo M (2010) A new spectral bound on the clique number of graphs. Hancock E, Wilson R, Windeatt T, Ulusoy I, Escolano F, eds. Structural, Syntactic, and Statistical Pattern Recognition, Lecture Notes in Computer Science, vol. 6218 (Springer, Berlin, Heidelberg), 680–689.Crossref, Google Scholar
• Carraghan R, Pardalos P (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375–382.Crossref, Google Scholar
• Cavique L (2007) A scalable algorithm for the market basket analysis. J. Retailing Consumer Services 14(6):400–407.Crossref, Google Scholar
• de Andrade MRQ, de Andrade PMF, Martins SL, Plastino A (2005) GRASP with path-relinking for the maximum diversity problem. Nikoletseas SE, ed. Experimental and Efficient Algorithms, Programming and Software Engineering, vol. 3503 (Springer, Berlin, Heidelberg), 558–569.Google Scholar
• Dijkhuizen G, Faigle U (1993) A cutting-plane approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. 69(1):121–130.Crossref, Google Scholar
• Fontes DBMM, Gonçalves JF, Fontes FACC (2018) An evolutionary approach to the maximum edge weight clique problem. Recent Adv. Electr. Electronic Engrg. 11(3):260–266.Crossref, Google Scholar
• Gallego M, Duarte A, Laguna M, Martí R (2007) Hybrid heuristics for the maximum diversity problem. Comput. Optim. Appl. 44(3):411–426.Crossref, Google Scholar
• Gendron B, Hertz A, St-Louis P (2008) A sequential elimination algorithm for computing bounds on the clique number of a graph. Discrete Optim. 5(3):615–628.Crossref, Google Scholar
• Gouveia L, Martins P (2015) Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO J. Comput. Optim. 3(1):1–30.Crossref, Google Scholar
• Hosseinian S, Fontes DBMM, Butenko S (2016) A quadratic approach to the maximum edge weight clique problem. Rocha AMAC, Costa MFP, Fernandes EMGP, eds. Proc. XIII Global Optim. Workshop (University of Minho, Braga, Portugal), 125–128.Google Scholar
• Hosseinian S, Fontes DBMM, Butenko S (2018) A nonconvex quadratic optimization approach to the maximum edge weight clique problem. J Global Optim. 72(2):219–240.Google Scholar
• Hosseinian S, Fontes DBMM, Butenko S, Buongiorno-Nardelli M, Fornari M, Curtarolo S (2017) The maximum edge weight clique problem: Formulations and solution approaches. Butenko S, Pardalos PM, Shylo V, eds. Optimization Methods and Applications: In Honor of Ivan V. Sergienko’s 80th Birthday (Springer International Publishing, Cham, Switzerland), 217–237.Crossref, Google Scholar
• Hunting M, Faigle U, Kern W (2001) A Lagrangian relaxation approach to the edge-weighted clique problem. Eur. J. Oper. Res. 131(1):119–131.Crossref, Google Scholar
• Jabbar MA, Deekshatulu BL, Chandra P (2013) Graph based approach for heart disease prediction. Das VV, ed. Proc. 3rd Internat. Conf. Trends Inform. Telecomm. Comput. (Springer, New York), 465–474.Google Scholar
• Johnson DS, Trick MA, eds. (1996) Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge (American Mathematical Society, Providence, RI)Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity of Computer Computations (Plenum Press, New York), 85–103.Crossref, Google Scholar
• Li CM, Quan Z (2010) An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. Proc. 24th AAAI Conf. Artificial Intelligence, vol. 10 (Association for the Advancement of Artificial Intelligence, Atlanta), 128–133.Google Scholar
• Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1):1–7.Crossref, Google Scholar
• Ma T, Latecki LJ (2012) Maximum weight cliques with mutex constraints for video object segmentation. 2012 IEEE Conf. Comput. Vision Pattern Recognition (IEEE Computer Society, Washington, DC), 670–677.Google Scholar
• Macambira EM, de Souza CC (2000) The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations. Eur. J. Oper. Res. 123(2):346–371.Crossref, Google Scholar
• Martí R, Gallego M, Duarte A (2010) A branch and bound algorithm for the maximum diversity problem. Eur. J. Oper. Res. 200(1):36–44.Crossref, Google Scholar
• Mehrotra A, Trick MA (1998) Cliques and clustering: A combinatorial approach. Oper. Res. Lett. 22(1):1–12.Crossref, Google Scholar
• Mycielski J (1955) Sur le coloriage des graphs. Colloquium Math. 3(2):161–162.Crossref, Google Scholar
• Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1–3):197–207.Crossref, Google Scholar
• Padberg M (1989) The Boolean quadric polytope: some characteristics, facets and relatives. Math. Programming 45(1–3):139–172.Crossref, Google Scholar
• Palubeckis G (2007) Iterated tabu search for the maximum diversity problem. Appl. Math. Comput. 189(1):371–383.Crossref, Google Scholar
• Park K, Lee K, Park S (1996) An extended formulation approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. 95(3):671–682.Crossref, Google Scholar
• Pavan M, Pelillo M (2003) Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation. Rangarajan A, Figueiredo M, Zerubia J, eds. Energy Minimization Methods in Computer Vision and Pattern Recognition—EMMCVPR 2003, Lecture Notes in Computer Science, vol. 2683 (Springer, Berlin, Heidelberg), 485–500.Google Scholar
• Pullan W (2006) Phased local search for the maximum clique problem. J. Combin. Optim. 12(3):303–323.Crossref, Google Scholar
• Pullan W (2008) Approximating the maximum vertex/edge weighted clique using local search. J. Heuristics 14(2):117–134.Crossref, Google Scholar
• San Segundo P, Nikolaev A, Batsyn M (2015) Infra-chromatic bound for exact maximum clique search. Comput. Oper. Res. 64:293–303.Crossref, Google Scholar
• San Segundo P, Rodrıiguez-Losada D, Jiménez A (2011) An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2):571–581.Crossref, Google Scholar
• Shimizu S, Yamaguchi K, Masuda S (2018) A maximum edge-weight clique extraction algorithm based on branch-and-bound. Preprint, submitted October 24, https://arxiv.org/abs/1810.10258. Google Scholar
• Shimizu S, Yamaguchi K, Masuda S (2019) A branch-and bound based exact algorithm for the maximum edge-weight clique problem. Lee R, ed. Computational Science/Intelligence & Applied Informatics, Studies in Computational Intelligence, vol. 787 (Springer International Publishing AG, Cham, Switzerland), 27–47.Crossref, Google Scholar
• Silva GC, de Andrade MRQ, Ochi LS, Martins SL, Plastino A (2007) New heuristics for the maximum diversity problem. J. Heuristics 13(4):315–336.Crossref, Google Scholar
• Sørensen MM (2004) New facets and a branch-and-cut algorithm for the weighted clique problem. Eur. J. Oper. Res. 154(1):57–70.Crossref, Google Scholar
• Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37(1):95–111.Crossref, Google Scholar
• Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Calude CS, Dinneen MJ, Vajnovszki V, eds. Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731 (Springer, Berlin, Heidelberg), 278–289.Google Scholar
• Tomita E, Sutani Y, Higashi T, Takahashi S, Wakatsuki M (2010) A simple and faster branch-and-bound algorithm for finding a maximum clique. Rahman MS, Fujita S, eds. WALCOM: Algorithms and Computation, Theoretical Computer Science and General Issues, vol. 5942 (Springer, Berlin, Heidelberg), 191–203.Google Scholar
• Wang Y, Hao JK, Glover F, Lü Z (2014) A tabu search based memetic algorithm for the maximum diversity problem. Engrg. Appl. Artificial Intelligence 27:103–114.Crossref, Google Scholar
• Wilf HS (1967) The eigenvalues of a graph and its chromatic number. J. London Math. Soc. 42(1):330–332.Crossref, Google Scholar
• Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3):693–709.Crossref, Google Scholar
• Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. Proc. 38th Annual ACM Sympos. Theory Comput. (ACM Press, New York), 681–690.Google Scholar