Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Algorithm Portfolios for Noisy Optimization: Compare Solvers Early Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Initial Sorting of Vertices in the Maximum Clique Problem Reviewed

Authors : Pablo San Segundo, Alvaro Lopez, Mikhail Batsyn

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In recent years there have been a number of important improvements in exact color-based maximum clique solvers, which have considerably enhanced their performance. Initial vertex ordering is one strategy known to have a significant impact on the size of the search tree. Typically, a degenerate sorting by minimum degree is used; literature also reports different tiebreaking strategies. A systematic study of the impact of initial sorting in the light of new cutting-edge ideas (e.g. recoloring [8], selective coloring [13], ILS initial lower bound computation [15, 16] or MaxSAT-based pruning [14]) is, however, lacking. This paper presents a new initial sorting procedure and relates performance to the new mentioned variants implemented in leading solver BBMC [9, 10].

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Multiple Decision Problem for Stock Selection in Market Network
next chapter Using Comparative Preference Statements in Hypervolume-Based Interactive Multiobjective Optimization
Footnotes
Literature
1.
Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173, 1–17 (2006)CrossRefMATHMathSciNet
2.
Hotta, K., Tomita, E., Takahashi, H.: A view invariant human FACE detection method based on maximum cliques. Trans. IPSJ 44(SIG14(TOM9)), 57–70 (2003)
3.
San Segundo, P., Rodriguez-Losada, D., Matia, F., Galan, R.: Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl. Intell. 32(3), 311–329 (2010)CrossRef
4.
San Segundo, P., Rodriguez-Losada, D.: Robust global feature based data association with a sparse bit optimized maximum clique algorithm. IEEE Trans. Rob. 29(5), 1332–1339 (2013)CrossRef
5.
Du, D., Pardalos, P.M.: Handbook of Combinatorial Optimization, Supplement, vol. A. Springer, New York (1999)CrossRef
6.
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRefMATH
7.
Carraghan, R., Pardalos, P.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375–382 (1990)CrossRefMATH
8.
Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Rahman, M., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191–203. Springer, Heidelberg (2010)CrossRef
9.
San Segundo, P., Rodriguez-Losada, D., Jimenez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571–581 (2011)CrossRefMATHMathSciNet
10.
San Segundo, P., Matia, F., Rodriguez-Losada, D., Hernando, M.: An improved bit parallel exact maximum clique algorithm. Optim. Lett. 7(3), 467–479 (2011)CrossRefMathSciNet
11.
12.
13.
San Segundo, P., Tapia, C.: Relaxed approximate coloring in exact maximum clique search. Comput. Oper. Res. 44, 185–192 (2014)CrossRefMathSciNet
14.
Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. In: Proceedings of AAAI-10, pp. 128–133
15.
Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525–547 (2012)CrossRef
16.
Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27(2), 397–416 (2014)CrossRefMATHMathSciNet
17.
Tomita, E., Seki, T.: An efficient branch and bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol. 2731, pp. 278–289. Springer, Heidelberg (2003)CrossRef
18.
San Segundo, P., Tapia, C.: A new implicit branching strategy for exact maximum clique. In: ICTAI, ICTAI Press, vol. 1, pp. 352–357 (2010)
19.
Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. Assoc. Comput. Mach. 30(3), 417–427 (1983)CrossRefMATHMathSciNet
20.
San Segundo, P., Nikolaaev, A., Batsyn, A.: Infra-chromatic bound for exact maximum clique search (2014). (Manuscript submitted for publication)
Metadata
Title
Initial Sorting of Vertices in the Maximum Clique Problem Reviewed
Authors
Pablo San Segundo
Alvaro Lopez
Mikhail Batsyn
Copyright Year
2014
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-319-09583-7

Electronic ISBN: 978-3-319-09584-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09584-4_12

Premium Partner

    Image Credits