.png){kind=icon}
返回
An exact algorithm for the minimum sum coloring problem on partially decomposable graphs
.png){kind=icon}
PRE
AI
DOI：10.1051/ro/2025140.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定一个无向图G，最小和着色问题(MSCP)要求使用自然数对G的顶点进行合法着色，以使颜色的总和最小化。本文提出了一种基于图G的模块分解树(MDT)的MSCP精确求解方法，该方法在过程结束时通过根节点获得最优解。该方法称为用于和着色的模块分解(MDSC)，源于如下观察：将图G分解为不相交的子图需要从每个子图中谨慎选择至少一个解，以贡献最终的最优解。模块分解技术有助于我们智能地进行这些选择。因此，分支定界过程在求解部分可分解图上的MSCP时变得更加高效、快速和强大。数值实验在几个大型DIMACS、COLOR 2002-2004挑战图以及我们生成的实例上证明了这一改进，每个实例包含500到1500个顶点。
Keyword:
Minimum sum coloring
strength of graph
proper coloration
modular decomposition
exact method
期刊
R
IF:
2.1
论文数:
103
被引数:
0
机构
暂无机构信息
引用论文
A New Sum Coloring-based Integer Linear Programming for Solving the University Course Timetabling Problem.png)
2020 International Multi-Conference on: “Organization of Knowledge and Advanced Technologies” (OCTA)
2020 International Multi-Conference on: “Organization of Knowledge and Advanced Technologies” (OCTA)IF0
PREAI
分享收藏Computing lower bounds for minimum sum coloring and optimum cost chromatic partition计算最小和着色和最佳成本色度分区的下界
PREAI
分享收藏
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations通过递归因子化排列实现更简单的线性时间模块化分解
PREAI
分享收藏
查看更多内容