.png){kind=icon}
返回
Solving the List Coloring Problem through a branch-and-price algorithm
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2024.01.038.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this work, we present a branch -and -price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. We propose two branching strategies based on others for the Graph Coloring Problem, the first is an adaptation of the one used by Mehrotra and Trick in their pioneering branch -and -price algorithm and the other is inspired by the one used by Mendez-Diaz and Zabala in their branch -and -cut algorithm. The rich structure of this problem makes both branching strategies robust. Extensive computation experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.
Keyword:
Combinatorial optimization
Integer programming
Weighted list coloring
Branch and price
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
分享收藏
Mechanical Properties of Fibre Reinforced Polymers under Elevated Temperatures: An Overview.png)
PolymersOAAI
PolymersIF0
OAAI分享收藏The effects of abscisic acid, kinetin and 5-fluorouracil on ribonucleic acid and protein synthesis in senescing radish leaf disksPlanta
PlantaIF0
PREAI
分享收藏
查看更多内容