顶点赋权图中的连通子图划分问题  

Connected Subgraph Partition in Vertex-weighted Graph

作　　者：李彤 陈永[1] 张安[1] 陈光亭[2] LI Tong;CHEN Yong;ZHANG An;CHEN Guangting(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

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

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

摘　　要：基于局部搜索技术,针对k=2时的连通子图划分问题,设计了多项式时间近似算法,理论上证明了算法的最坏情况界为4/3,并给出了紧例。Based on the local search technique,apolynomial time approximation algorithm is designed for the problem of connected subgraph partitioning for the case that k=2.The worst case ratio of the algorithm is proved to be 4/3,and a tight instance is also provided.

关 键 词：图划分 连通子图 近似算法 最坏情况界 

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