4-正则图上的最小连通顶点覆盖问题  被引量:1

The Minimum Connected Vertex Cover Problem in 4-regular Graphs

在线阅读下载全文

作  者:许梦宇 张安[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[理学—运筹学与控制论]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象