nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

A Branch-and-Bound Based Exact Algorithm for the Maximum Edge-Weight Clique Problem

verfasst von : Satoshi Shimizu, Kazuaki Yamaguchi, Sumio Masuda

Erschienen in: Computational Science/Intelligence & Applied Informatics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The maximum edge-weight clique problem is to find a clique whose sum of edge-weight is maximum for a given edge-weighted undirected graph. The problem is NP-hard and was formulated as a mathematical programming problem in previous studies. In this paper, we propose an exact algorithm based on branch-and-bound. By some computational experiments, we confirmed our proposal algorithm is faster than the methods based on mathematical programming.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Python Deserialization Denial of Services Attacks and Their Mitigations

Nächstes Kapitel A Software Model for Precision Agriculture Framework Based on Smart Farming System and Application of IoT Gateway

Alidaee, B., Glover, F., Kochenberger, G., Wang, H.: Solving the maximum edge weight clique problem via unconstrained quadratic programming. Eur. J. Oper. Res. 181(2), 592–597 (2007)CrossRef

Aringhieri, R., Bruglieri, M., Cordone, R.: Optimal results and tight bounds for the maximum diversity problem. Found. Comput. Decis. Sci. 34(2), 73 (2009)MATH

Bahadur, K., Akutsu, T., Tomita, E., Seki, T.: Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach. In: The Second Conference on Asia-Pacific Bioinformatics, vol. 29, pp. 191–200. Australian Computer Society, Inc. (2004)

Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.M.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27(2), 397–416 (2014)MathSciNetCrossRef

Bogdanova, G.T., Brouwer, A.E., Kapralov, S.N., Östergård, P.R.: Error-correcting codes over an alphabet of four elements. Des. Codes Cryptogr. 23(3), 333–342 (2001)MathSciNetCrossRef

Brown, J., Dukka Bahadur, K., Tomita, E., Akutsu, T.: Multiple methods for protein side chain packing using maximum weight cliques. Genome Inf. 17(1), 3–12 (2006)

Brown, K.L.: Combinatorial auction test suite (CATS) (2000). http://www.cs.ubc.ca/~kevinlb/CATS/

Cavique, L.: A scalable algorithm for the market basket analysis. J. Retail. Consum. Serv. 14(6), 400–407 (2007)CrossRef

Corman, S.R., Kuhn, T., McPhee, R.D., Dooley, K.J.: Studying complex discursive systems. Hum. Commun. Res. 28(2), 157–206 (2002)

10.

Corman, S.R., et al.: Pajek datasets: reuters terror news network. http://vlado.fmf.uni-lj.si/pub/networks/data/CRA/terror.htm

11.

Fang, Z., Li, C.M., Xu, K.: An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem. J. Artif. Intell. Res. 55, 799–833 (2016)MathSciNetCrossRef

12.

Gary, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)

13.

Gouveia, L., Martins, P.: Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. Eur. J. Comput. Optim. 3(1), 1–30 (2015)MathSciNetCrossRef

14.

Horaud, R., Skordas, T.: Stereo correspondence through feature grouping and maximal cliques. IEEE Trans. Pattern Anal. Mach. Intell. 11(11), 1168–1180 (1989)CrossRef

15.

Kc, D.B., Akutsu, T., Tomita, E., Seki, T., Fujiyama, A.: Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms. Genome Inf. 13, 143–152 (2002)

16.

Li, C.M., Jiang, H., Manyà, F.: On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. Comput. Oper. Res. 84, 1–15 (2017)MathSciNetCrossRef

17.

Martí, R., Gallego, M., Duarte, A.: A branch and bound algorithm for the maximum diversity problem. Eur. J. Oper. Res. 200(1), 36–44 (2010)CrossRef

18.

McCreesh, C., Prosser, P., Simpson, K., Trimble, J.: On maximum weight clique algorithms, and how they are evaluated. In: International Conference on Principles and Practice of Constraint Programming, pp. 206–225. Springer (2017)

19.

Östergård, P.R.: A new algorithm for the maximum-weight clique problem. Nordic J. Comput. 8(4), 424–436 (2001)MathSciNet

20.

Park, K., Lee, K., Park, S.: An extended formulation approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. 95(3), 671–682 (1996)CrossRef

21.

Pullan, W.: Approximating the maximum vertex/edge weighted clique using local search. J. Heuristics 14(2), 117–134 (2008)CrossRef

22.

San Segundo, P., Rodríguez-Losada, D., Jiménez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571–581 (2011)MathSciNetCrossRef

23.

Shimizu, S., Yamaguchi, K., Masuda, S.: Mathematical programming formulation for the maximum edge-weight clique problem. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (in Japanese) J100-A(8), 313–315 (2017)

24.

Shimizu, S., Yamaguchi, K., Saitoh, T., Masuda, S.: Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound. Descr. Appl. Math. 223, 120–134 (2017)MathSciNetCrossRef

25.

Sørensen, M.M.: New facets and a branch-and-cut algorithm for the weighted clique problem. Eur. J. Oper. Res. 154(1), 57–70 (2004)MathSciNetCrossRef

26.

Sorour, S., Valaee, S.: Minimum broadcast decoding delay for generalized instantly decodable network coding. In: Global Telecommunications Conference (GLOBECOM 2010), pp. 1–5. IEEE (2010)

27.

Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95–111 (2007)MathSciNetCrossRef

28.

Tomita, E., Yoshida, K., Hatta, T., Nagao, A., Ito, H., Wakatsuki, M.: A much faster branch-and-bound algorithm for finding a maximum clique. In: International Workshop on Frontiers in Algorithmics, pp. 215–226. Springer (2016)

29.

Trick, M., Chvatal, V., Cook, B., Johnson, D., McGeoch, C., Tarjan, B., et al.: DIMACS implementation challenges. http://dimacs.rutgers.edu/Challenges/

30.

Yamaguchi, K., Masuda, S.: A new exact algorithm for the maximum weight clique problem. In: 23rd International Conference on Circuits/Systems, Computers and Communications (ITC-CSCC08), pp. 317–320 (2008)

Titel: A Branch-and-Bound Based Exact Algorithm for the Maximum Edge-Weight Clique Problem
verfasst von: Satoshi Shimizu
Kazuaki Yamaguchi
Sumio Masuda
Verlag: Springer International Publishing
Buch: Computational Science/Intelligence & Applied Informatics
Print ISBN: 978-3-319-96805-6

Electronic ISBN: 978-3-319-96806-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-319-96806-3_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"