# An Ant Algorithm for the Partition Graph Coloring Problem

Ontology type: schema:Chapter

### Chapter Info

DATE

2015-02-04

AUTHORS ABSTRACT

In this paper we propose an Ant Colony Optimization (ACO) algorithm for the partition graph coloring problem (PGCP). Given an undirected graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G =(V,E)$$\end{document}, whose nodes are partition into a given number of the node sets. The goal of the PGCP is to find a subset \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^* \subset V$$\end{document} that contains exactly one node for each cluster and a coloring for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^*$$\end{document} so that in the graph induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^*$$\end{document}, 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. More... »

PAGES

78-84

### Book

TITLE

Numerical Methods and Applications

ISBN

978-3-319-15584-5
978-3-319-15585-2

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-15585-2_9

DOI

http://dx.doi.org/10.1007/978-3-319-15585-2_9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1053332177

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Bulgarian Academy of Sciences, Sofia, Bulgaria",
"id": "http://www.grid.ac/institutes/grid.410344.6",
"name": [
"Bulgarian Academy of Sciences, Sofia, Bulgaria"
],
"type": "Organization"
},
"familyName": "Fidanova",
"givenName": "Stefka",
"id": "sg:person.011173106320.18",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011173106320.18"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Computer Science, North University Center at Baia Mare, Technical University of Cluj-Napoca, Cluj-Napoca, Romania",
"id": "http://www.grid.ac/institutes/grid.6827.b",
"name": [
"Department of Mathematics and Computer Science, North University Center at Baia Mare, Technical University of Cluj-Napoca, Cluj-Napoca, Romania"
],
"type": "Organization"
},
"familyName": "Pop",
"givenName": "Petric\u0103 C.",
"id": "sg:person.012327271025.76",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012327271025.76"
],
"type": "Person"
}
],
"datePublished": "2015-02-04",
"datePublishedReg": "2015-02-04",
"description": "In this paper we propose an Ant Colony Optimization (ACO) algorithm for the partition graph coloring problem (PGCP). Given an undirected graph \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G =(V,E)$$\\end{document}, whose nodes are partition into a given number of the node sets. The goal of the PGCP is to find a subset \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$V^* \\subset V$$\\end{document} that contains exactly one node for each cluster and a coloring for \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$V^*$$\\end{document} so that in the graph induced by \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$V^*$$\\end{document}, 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.",
"editor": [
{
"familyName": "Dimov",
"givenName": "Ivan",
"type": "Person"
},
{
"familyName": "Fidanova",
"givenName": "Stefka",
"type": "Person"
},
{
"familyName": "Lirkov",
"givenName": "Ivan",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-15585-2_9",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-15584-5",
"978-3-319-15585-2"
],
"name": "Numerical Methods and Applications",
"type": "Book"
},
"keywords": [
"graph coloring problem",
"coloring problem",
"ant colony optimization algorithm",
"colony optimization algorithm",
"optimization algorithm",
"undirected graph",
"ACO algorithm",
"computational results",
"benchmark instances",
"ant algorithm",
"art algorithms",
"node set",
"algorithm",
"graph",
"problem",
"solid results",
"common benchmark instances",
"coloring",
"nodes",
"partition",
"number",
"set",
"clusters",
"results",
"instances",
"total number",
"different colors",
"performance",
"state",
"subset",
"goal",
"color",
"paper"
],
"name": "An Ant Algorithm for the Partition Graph Coloring Problem",
"pagination": "78-84",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1053332177"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-15585-2_9"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-15585-2_9",
"https://app.dimensions.ai/details/publication/pub.1053332177"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:47",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_412.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-15585-2_9"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15585-2_9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15585-2_9'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15585-2_9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15585-2_9'

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N39cdd95c05c94a3a97835d2320de358e
4 schema:datePublished 2015-02-04
5 schema:datePublishedReg 2015-02-04
6 schema:description In this paper we propose an Ant Colony Optimization (ACO) algorithm for the partition graph coloring problem (PGCP). Given an undirected graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G =(V,E)$$\end{document}, whose nodes are partition into a given number of the node sets. The goal of the PGCP is to find a subset \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^* \subset V$$\end{document} that contains exactly one node for each cluster and a coloring for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^*$$\end{document} so that in the graph induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^*$$\end{document}, 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.
7 schema:editor N1005acf4815e46a8ab7a6389daf025ff
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3d4f90f535054465b24b469da0f6fb30
12 schema:keywords ACO algorithm
14 algorithm
15 ant algorithm
16 ant colony optimization algorithm
17 art algorithms
18 benchmark instances
19 clusters
20 colony optimization algorithm
21 color
22 coloring
23 coloring problem
24 common benchmark instances
25 computational results
26 different colors
27 goal
28 graph
29 graph coloring problem
30 instances
31 node set
32 nodes
33 number
34 optimization algorithm
35 paper
36 partition
37 performance
38 problem
39 results
40 set
41 solid results
42 state
43 subset
44 total number
45 undirected graph
46 schema:name An Ant Algorithm for the Partition Graph Coloring Problem
47 schema:pagination 78-84
48 schema:productId N056ee6a403624e249f17b785e7907afb
49 N11ece070910141f5aa82dc4d29d30d56
50 schema:publisher N116a5c770c3a4e6ab14fcb200989c754
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053332177
52 https://doi.org/10.1007/978-3-319-15585-2_9
53 schema:sdDatePublished 2022-05-20T07:47
55 schema:sdPublisher N30e2a675a0214751aa75058fb53ec03d
56 schema:url https://doi.org/10.1007/978-3-319-15585-2_9
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N03ec204a43ed4c0dbb00a8dd1a7fc77d schema:familyName Dimov
61 schema:givenName Ivan
62 rdf:type schema:Person
63 N056ee6a403624e249f17b785e7907afb schema:name dimensions_id
64 schema:value pub.1053332177
65 rdf:type schema:PropertyValue
66 N0b5fa6931b744d398be43ac05f3b4298 rdf:first Nf1d0a384de1f42b78a509172f8764ff5
67 rdf:rest Nf9d87e5e9a9d424fb1df603aae666822
68 N1005acf4815e46a8ab7a6389daf025ff rdf:first N03ec204a43ed4c0dbb00a8dd1a7fc77d
69 rdf:rest N0b5fa6931b744d398be43ac05f3b4298
70 N116a5c770c3a4e6ab14fcb200989c754 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N11ece070910141f5aa82dc4d29d30d56 schema:name doi
73 schema:value 10.1007/978-3-319-15585-2_9
74 rdf:type schema:PropertyValue
75 N30e2a675a0214751aa75058fb53ec03d schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N39cdd95c05c94a3a97835d2320de358e rdf:first sg:person.011173106320.18
78 rdf:rest N3c36814e60e24938a7acd03f865e99ba
79 N3c36814e60e24938a7acd03f865e99ba rdf:first sg:person.012327271025.76
80 rdf:rest rdf:nil
81 N3d4f90f535054465b24b469da0f6fb30 schema:isbn 978-3-319-15584-5
82 978-3-319-15585-2
83 schema:name Numerical Methods and Applications
84 rdf:type schema:Book
85 Nc4a8d5c494ca4c9288604319c81da8c9 schema:familyName Lirkov
86 schema:givenName Ivan
87 rdf:type schema:Person
88 Nf1d0a384de1f42b78a509172f8764ff5 schema:familyName Fidanova
89 schema:givenName Stefka
90 rdf:type schema:Person
91 Nf9d87e5e9a9d424fb1df603aae666822 rdf:first Nc4a8d5c494ca4c9288604319c81da8c9
92 rdf:rest rdf:nil
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
97 schema:name Computation Theory and Mathematics
98 rdf:type schema:DefinedTerm
99 sg:person.011173106320.18 schema:affiliation grid-institutes:grid.410344.6
100 schema:familyName Fidanova
101 schema:givenName Stefka
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011173106320.18
103 rdf:type schema:Person
104 sg:person.012327271025.76 schema:affiliation grid-institutes:grid.6827.b
105 schema:familyName Pop
106 schema:givenName Petrică C.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012327271025.76
108 rdf:type schema:Person
109 grid-institutes:grid.410344.6 schema:alternateName Bulgarian Academy of Sciences, Sofia, Bulgaria
110 schema:name Bulgarian Academy of Sciences, Sofia, Bulgaria
111 rdf:type schema:Organization
112 grid-institutes:grid.6827.b schema:alternateName Department of Mathematics and Computer Science, North University Center at Baia Mare, Technical University of Cluj-Napoca, Cluj-Napoca, Romania
113 schema:name Department of Mathematics and Computer Science, North University Center at Baia Mare, Technical University of Cluj-Napoca, Cluj-Napoca, Romania
114 rdf:type schema:Organization