CSpace  > 应用数学研究所
Finding connected kappa-subgraphs with high density
Chen, Xujin1; Hua, Xiaodong1; Wang, Changjun2
AbstractGiven an edge-weighted connected graph G on n vertices and a positive integer k <= n, 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 Omega(max{1/k, k(2)/n(2)}) of the maximum weighted density among all k-subgraph in G(which are not necessarily connected), where max{1/k, k(2)/n(2)} >= n(-2/3) implies an O(n(2/3))-approximation ratio. We obtain improved O(n(2/5))-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 O(root nlogn)-approximation for the problem on general weighted interval graphs. (C) 2017 Elsevier Inc. All rights reserved.k
KeywordDensest kappa-subgraphs Heaviest kappa-subgraphs Connectivity Approximation algorithms Interval graphs
Funding ProjectNNSF of China[11531014] ; NNSF of China[11601022] ; Open Fund of Beijing Institute for Scientific and Engineering Computing
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Mathematics, Applied
WOS IDWOS:000412282400014
Citation statistics
Document Type期刊论文
Corresponding AuthorWang, Changjun
Affiliation1.Chinese Acad Sci, Inst Appl Math, AMSS, Beijing 100190, Peoples R China
2.Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
Recommended Citation
GB/T 7714
Chen, Xujin,Hua, Xiaodong,Wang, Changjun. Finding connected kappa-subgraphs with high density[J]. INFORMATION AND COMPUTATION,2017,256:160-173.
APA Chen, Xujin,Hua, Xiaodong,&Wang, Changjun.(2017).Finding connected kappa-subgraphs with high density.INFORMATION AND COMPUTATION,256,160-173.
MLA Chen, Xujin,et al."Finding connected kappa-subgraphs with high density".INFORMATION AND COMPUTATION 256(2017):160-173.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Chen, Xujin]'s Articles
[Hua, Xiaodong]'s Articles
[Wang, Changjun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Chen, Xujin]'s Articles
[Hua, Xiaodong]'s Articles
[Wang, Changjun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Chen, Xujin]'s Articles
[Hua, Xiaodong]'s Articles
[Wang, Changjun]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.