检索规则说明:AND代表“并且”;OR代表“或者”;NOT代表“不包含”;(注意必须大写,运算符两边需空一格)
检 索 范 例 :范例一: (K=图书馆学 OR K=情报学) AND A=范并思 范例二:J=计算机应用与软件 AND (U=C++ OR U=Basic) NOT M=Visual
作 者:许梦宇 张安[1] 陈永[1] 陈光亭[2] XU Mengyu;ZHANG An;CHEN Yong;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年第5期83-87,97,共6页Journal of Hangzhou Dianzi University:Natural Sciences
基 金:国家自然科学基金资助项目(11771114,11571252)。
摘 要:任给一个4-正则图,研究如何寻找4-正则图顶点数目最少的顶点覆盖问题,使其导出子图是一个连通图。已研究证明该问题是NP-难的且存在最坏情况界不超过4/3+O(1/n)的近似算法,其中n为4-正则图的顶点数。在此基础上,提出该算法的一个改进分析,使其最坏情况界中的O(1/n)项得以舍去。Given a 4-regular graph,it aims to find a vertex cover with the minimum number of vertices provided that the induced graph of the vertex cover is connected.It has been shown to be NP-hard and admits an approximation algorithm with worst-case ratio no more than 4/3+O(1/n),where n is the number of vertices of the 4-regular graph.This paper provides an improved algorithm with a tighter worst-case ratio,where the additive term O(1/n)could be removed.
分 类 号:O221.7[理学—运筹学与控制论]
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在链接到云南高校图书馆文献保障联盟下载...
云南高校图书馆联盟文献共享服务平台 版权所有©
您的IP:216.73.216.28