Essec\Faculty\Model\Contribution {#6196
#_index: "academ_contributions"
#_id: "12158"
#_source: array:26 [
"id" => "12158"
"slug" => "a-branch-and-price-algorithm-for-the-robust-graph-coloring-problem"
"yearMonth" => "2014-03"
"year" => "2014"
"title" => "A branch-and-price algorithm for the robust graph coloring problem"
"description" => "ARCHETTI, C., BIANCHESSI, N. et HERTZ, A. (2014). A branch-and-price algorithm for the robust graph coloring problem. <i>Discrete Applied Mathematics</i>, 165, pp. 49-59."
"authors" => array:3 [
0 => array:3 [
"name" => "ARCHETTI Claudia"
"bid" => "B00773540"
"slug" => "archetti-claudia"
]
1 => array:1 [
"name" => "BIANCHESSI Nicola"
]
2 => array:1 [
"name" => "HERTZ Alain"
]
]
"ouvrage" => ""
"keywords" => array:4 [
0 => "Graph coloring"
1 => "Robust solution"
2 => "Branch-and-price algorithm"
3 => "Tabu search"
]
"updatedAt" => "2021-07-13 14:32:01"
"publicationUrl" => "https://doi.org/10.1016/j.dam.2013.02.013"
"publicationInfo" => array:3 [
"pages" => "49-59"
"volume" => "165"
"number" => ""
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "Given a graph , an integer , and a cost associated with all pairs of non-adjacent vertices in , the robust graph coloring problem is to assign a color in to every vertex of so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances."
"en" => "Given a graph , an integer , and a cost associated with all pairs of non-adjacent vertices in , the robust graph coloring problem is to assign a color in to every vertex of so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
"en" => "Information Systems, Decision Sciences and Statistics"
]
"indexedAt" => "2024-03-29T09:22:01.000Z"
"docTitle" => "A branch-and-price algorithm for the robust graph coloring problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/archetti-claudia">ARCHETTI Claudia</a>, BIANCHESSI Nicola, HERTZ Alain"
"docDescription" => "<span class="document-property-authors">ARCHETTI Claudia, BIANCHESSI Nicola, HERTZ Alain</span><br><span class="document-property-authors_fields">Systèmes d’Information, Sciences de la Décision et Statistiques</span> | <span class="document-property-year">2014</span>"
"keywordList" => "<a href="#">Graph coloring</a>, <a href="#">Robust solution</a>, <a href="#">Branch-and-price algorithm</a>, <a href="#">Tabu search</a>"
"docPreview" => "<b>A branch-and-price algorithm for the robust graph coloring problem</b><br><span>2014-03 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.dam.2013.02.013" target="_blank">A branch-and-price algorithm for the robust graph coloring problem</a>"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.739312
+"parent": null
}