Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Machine Learning: Multi-site Evidence-Based Best Practice Discovery Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

An Enhanced Infra-Chromatic Bound for the Maximum Clique Problem

verfasst von : Pablo San Segundo, Jorge Artieda, Rafael Leon, Cristobal Tapia

Erschienen in: Machine Learning, Optimization, and Big Data

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

There has been a rising interest in experimental exact algorithms for the maximum clique problem because the gap between the expected theoretical performance and the reported results in practice is becoming surprisingly large. One reason for this is the family of bounding functions denoted as infra-chromatic because they produce bounds which can be lower than the chromatic number of the bounded subgraph. In this paper we describe a way to enhance exact solvers with an additional infra-chromatic bounding function and report performance over a number of graphs from well known data sets. Moreover, the reported results show that the new enhanced procedure significantly outperforms state-of-the-art.

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 Optimizing the Location of Helicopter Emergency Medical Service Operating Sites
Nächstes Kapitel Cultural Ant Colony Optimization on GPUs for Travelling Salesman Problem
Fußnoten
Literatur
1.
Bomze, I., Budinich, M., Pardalos, P., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 4, pp. 1–74. Springer, New York (1999)CrossRef
2.
Butenko, S., Chaovalitwongse, W., Pardalos, P. (eds.): Clustering Challenges in Biological Networks. World Scientific, Singapore (2009)
3.
San Segundo, P., Rodriguez-Losada, P., Matia, D., 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. Robot. 99, 1–7 (2013)
5.
San Segundo, P., Artieda, J.: A novel clique formulation for the visual feature matching problem. Appl. Intell. 43(2), 325–342 (2015)CrossRef
6.
Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 485–498. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45749-6_​44 CrossRef
7.
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). doi:10.​1007/​3-540-45066-1_​22 CrossRef
8.
Segundo, S., Rodriguez-Losada, D, Jimenez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571–581 (2011)MathSciNetCrossRefMATH
9.
San Segundo, P., Matia, F., Rodriguez-Losada, D., Hernando, M.: An improved bit parallel exact maximum clique algorithm. Optim. Lett. 7(3), 467–479 (2013)MathSciNetCrossRefMATH
10.
San Segundo, P., Tapia, C.: Relaxed approximate coloring in exact maximum clique search. Comput. Oper. Res. 44, 185–192 (2014)MathSciNetCrossRefMATH
11.
San Segundo, P., Nikolaev, A., Batsyn, M.: Infra-chromatic bound for exact maximum clique search. Comput. Oper. Res. 64, 293–303 (2015)MathSciNetCrossRefMATH
12.
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, Md.S, Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191–203. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-11440-3_​18 CrossRef
13.
Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27, 397–416 (2014)MathSciNetCrossRefMATH
14.
Li, C.-M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: Proceedings of ICTAI, pp. 344–351 (2010)
15.
Li, C.-M., Fang, Z., Xu, K.: Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. In: Proceedings of ICTAI, pp. 939–946 (2013)
16.
Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and nonapproximability — towards tight results. In: 1995 Proceedings of 36th Annual Symposium on Foundations of Computer Science, pp. 422–431. IEEE (1995)
17.
18.
Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. Technical report, Computer Science Department, School of Humanities and Sciences, Stanford University, Stanford, CA, USA (1976)
19.
Robson, J.M.: Finding a maximum independent set in time \( O(2^{{{n \mathord{\left/ {\vphantom {n 4}} \right. \kern-0pt} 4}}} ) \). Technical report 1251-01, LaBRI, Université de Bordeaux I (2001)
20.
Lavnikevich, N.: On the complexity of maximum clique algorithms: usage of coloring heuristics leads to the \( \Omega \left( {2^{{{n \mathord{\left/ {\vphantom {n 5}} \right. \kern-0pt} 5}}} } \right) \) algorithm running time lower bound (2013)
21.
22.
Metadaten
Titel
An Enhanced Infra-Chromatic Bound for the Maximum Clique Problem
verfasst von
Pablo San Segundo
Jorge Artieda
Rafael Leon
Cristobal Tapia
Copyright-Jahr
2016
Buch
Machine Learning, Optimization, and Big Data

Print ISBN: 978-3-319-51468-0

Electronic ISBN: 978-3-319-51469-7

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-51469-7_26

Premium Partner

    Bildnachweise