Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "13124"
#_source: array:26 [
"id" => "13124"
"slug" => "13124-a-branch-cut-algorithm-for-the-minimum-adjacency-vertex-coloring-problem"
"yearMonth" => "2011-11"
"year" => "2011"
"title" => "A branch & cut algorithm for the minimum-adjacency vertex coloring problem"
"description" => "DELLE DONNE, D. et MARENCO, J. (2011). A branch & cut algorithm for the minimum-adjacency vertex coloring problem. <i>Discrete Optimization</i>, 8(4), pp. 540-554. 
DELLE DONNE, D. et MARENCO, J. (2011). A branch & cut algorithm for the minimum-adjacency vertex col "
"authors" => array:2 [
0 => array:3 [
"name" => "DELLE DONNE Diego"
"bid" => "B00788133"
"slug" => "delle-donne-diego"
]
1 => array:1 [
"name" => "MARENCO Javier"
]
]
"ouvrage" => ""
"keywords" => array:3 [
0 => "Frequency assignment"
1 => "Adjacent colors"
2 => "Integer programming"
]
"updatedAt" => "2023-01-27 01:00:44"
"publicationUrl" => "https://doi.org/10.1016/j.disopt.2011.05.003"
"publicationInfo" => array:3 [
"pages" => "540-554"
"volume" => "8"
"number" => "4"
]
"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" => "In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results. In this work we study a particular way of dealing with interference in combinatorial optimization mo "
"en" => "In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results. In this work we study a particular way of dealing with interference in combinatorial optimization mo "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-08T19:21:39.000Z"
"docTitle" => "A branch & cut algorithm for the minimum-adjacency vertex coloring problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/delle-donne-diego">DELLE DONNE Diego</a>, MARENCO Javier"
"docDescription" => "<span class="document-property-authors">DELLE DONNE Diego, MARENCO Javier</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2011</span> <span class="document-property-authors">DELLE DONNE Diego, MARENCO Javier</span><br><span class="doc "
"keywordList" => "<a href="#">Frequency assignment</a>, <a href="#">Adjacent colors</a>, <a href="#">Integer programming</a> <a href="#">Frequency assignment</a>, <a href="#">Adjacent colors</a>, <a href="#">Integer programmi "
"docPreview" => "<b>A branch & cut algorithm for the minimum-adjacency vertex coloring problem</b><br><span>2011-11 | Articles </span> <b>A branch & cut algorithm for the minimum-adjacency vertex coloring problem</b><br><span>2011-11 | "
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.disopt.2011.05.003" target="_blank">A branch & cut algorithm for the minimum-adjacency vertex coloring problem</a> <a href="https://doi.org/10.1016/j.disopt.2011.05.003" target="_blank">A branch & cut algorithm for "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.764553
+"parent": null
}
