摘要
边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。
Given a simple undirected edge-colored graph,the maximum weak proper tree aims to find a weak proper tree spanning the largest possible number of vertices.This problem is NP-hard.By using the optimal properties of weakly proper trees and edge-colored graphs,the problem is discussed from the perspective of approximation algorithm by limiting the color number of colored edges to 2.A polynomial time approximation algorithm with worst-case ratio 2 is designed.A tight example of the approximation algorithm and its analysis are proposed.
作者
金世豪
陈光亭
陈永
张安
JIN Shihao;CHEN Guangting;CHEN Yong;ZHANG An(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China;School of Electronics and Information Engineering,Taizhou University,Taizhou Zhejiang 318000,China)
出处
《杭州电子科技大学学报（自然科学版）》
2021年第4期88-91,102,共5页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11971139,11771114)。
关键词
边着色图
近似算法
最坏情况界
树
edge-colored graph
approximation algorithm
worst case ratio
tree
