-
题名动态图染色问题研究
- 1
-
-
作者
邱雅娴
郝元宵
周军锋
杜明
-
机构
东华大学计算机学院
燕山大学信息科学与工程学院
-
出处
《智能计算机与应用》
2022年第3期5-11,共7页
-
基金
国家自然科学基金(61472339,61572421,61272124)
上海市自然科学基金(20ZR1402700)
-
文摘
图染色是指在一个连通的无向图中,为每个结点指定一个颜色,使得在任意两相邻结点颜色不相同的前提下,使用最少颜色进行染色的问题。针对已有静态染色方法无法处理动态图,并且已有动态图染色方法效率较差的问题,提出了批量处理更新的高效染色方法,以及保证染色效果的无索引方法,来降低内存消耗。经在4个真实数据集上进行实验,从染色质量、染色效率、内存消耗角度验证了本文算法的有效性。
-
关键词
图染色
动态图染色
贪心算法
-
Keywords
graph coloring
dynamic graph coloring
greedy algorithm
-
分类号
O157.5
[理学—基础数学]
-