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

作     者：李彤 陈永 张安 陈光亭 LI Tong;CHEN Yong;ZHANG An;CHEN Guangting

作者机构：杭州电子科技大学理学院浙江杭州310018 台州学院电子与信息工程学院浙江台州318000 

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

出 版 物：《杭州电子科技大学学报（自然科学版）》 (Journal of Hangzhou Dianzi University：Natural Sciences)

年 卷 期：2020年第40卷第4期

页      码：91-94页

摘      要：基于局部搜索技术,针对k=2时的连通子图划分问题,设计了多项式时间近似算法,理论上证明了算法的最坏情况界为4/3,并给出了紧例。

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.13954/j.cnki.hdu.2020.04.016

馆 藏 号：203955804...