边着色图上最大弱适当树问题近似算法

作者：金世豪; 陈光亭; 陈永^*; 张安

来源：杭州电子科技大学学报(自然科学版), 2021, 41(04): 88-102.

DOI：10.13954/j.cnki.hdu.2021.04.015

• 边着色图
• 近似算法
• 最坏情况界
• 树

边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。

• 单位
  台州学院