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

Approximation algorithm for the maximum weakly proper tree in edge-colored graphs

作　　者：金世豪 陈光亭[2] 陈永[1] 张安[1] 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)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]台州学院电子与信息工程学院,浙江台州318000

出　　处：《杭州电子科技大学学报（自然科学版）》2021年第4期88-91,102,共5页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11971139,11771114)。

摘　　要：边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找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.

关 键 词：边着色图 近似算法 最坏情况界 树 

分 类 号：O221.7[理学—运筹学与控制论]