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:
A Note on Local Refinement for Direction Splitting Methods Read chapter Read first chapter

2015 | OriginalPaper | Chapter

An Ant Algorithm for the Partition Graph Coloring Problem

Authors : Stefka Fidanova, Petrică C. Pop

Published in: Numerical Methods and Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In this paper we propose an Ant Colony Optimization (ACO) algorithm for the partition graph coloring problem (PGCP). Given an undirected graph \(G =(V,E)\), whose nodes are partition into a given number of the node sets. The goal of the PGCP is to find a subset \(V^* \subset V\) that contains exactly one node for each cluster and a coloring for \(V^*\) so that in the graph induced by \(V^*\), two adjacent nodes have different colors and the total number of used colors is minimal. The performance of our algorithm is evaluated on a common benchmark instances set and the computational results show that compared to a state-of-the-art algorithms, our ACO algorithm achieves solid results in very short run-times.

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 On Meme Self-Adaptation in Spatially-Structured Multimemetic Algorithms
next chapter Multi-exchange Neighborhoods for the Capacitated Ring Tree Problem
Literature
1.
Demange, M., Monnot, J., Pop, P., Ries, B.: Selective graph coloring in some special classes of graphs. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 320–331. Springer, Heidelberg (2012) CrossRef
2.
Demange, M., Monnot, J., Pop, P.C., Ries, B.: On the complexity of the selective graph coloring problem in some special classes of graphs. Theoret. Comput. Sci. 540–541, 89–102 (2014)CrossRefMathSciNet
3.
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)CrossRef
4.
Feremans, C., Labbé, M., Laporte, G.: Generalized network design problems. Eur. J. Oper. Res. 148, 1–13 (2003)CrossRefMATH
5.
Frota, Y., Maculan, N., Noronha, T.F., Ribeiro, C.C.: A branch-and-cut algorithm for the partition coloring problem. Networks 55(3), 194–204 (2010)MATHMathSciNet
6.
7.
8.
Hoshino, E.A., Frota, Y.A., de Souza, C.C.: A branch-and-price approach for the partition coloring problem. Oper. Res. Lett. 39(2), 132–137 (2011)CrossRefMATHMathSciNet
9.
Li, G., Simha, R.: The partition coloring problem and its application to wavelength routing and assignment. In: 1st Workshop on Optical Networks (2000)
10.
Noronha, T.F., Ribeiro, C.C.: Routing and wavelength assignment by partition colouring. Eur. J. Oper. Res. 171(3), 797–810 (2006)CrossRefMATHMathSciNet
11.
Pop, P.C.: Generalized Network Design Problems. Modeling and Optimization, De Gruyter Series in Discrete Mathematics and Applications, Germany (2012) CrossRefMATH
12.
Pop, P.C., Hu, B., Raidl, G.R.: A memetic algorithm with two distinct solution representations for the partition graph coloring problem. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) EUROCAST. LNCS, vol. 8111, pp. 219–226. Springer, Heidelberg (2013) CrossRef
Metadata
Title
An Ant Algorithm for the Partition Graph Coloring Problem
Authors
Stefka Fidanova
Petrică C. Pop
Copyright Year
2015
Book
Numerical Methods and Applications

Print ISBN: 978-3-319-15584-5

Electronic ISBN: 978-3-319-15585-2

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-15585-2_9

Premium Partner

    Image Credits