-
61浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
Finding connected k-subgraphs with high density
Information and Computation,2017,256():160-173 | 2017年10月01日 | https://doi.org/10.1016/j.ic.2017.07.003
Given an edge-weighted connected graph G on n vertices and a positive integer , a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where implies an -approximation ratio. We obtain improved -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give -approximation for the problem on general weighted interval graphs.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果