Finding connected kappa-subgraphs with high density

doi:10.1016/j.ic.2017.07.003

CSpace > 应用数学研究所

	Finding connected kappa-subgraphs with high density
	Chen, Xujin1 ; Hua, Xiaodong 1; Wang, Changjun 2
	2017-10-01
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	256 页码:160-173
摘要	Given 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
关键词	Densest kappa-subgraphs Heaviest kappa-subgraphs Connectivity Approximation algorithms Interval graphs
DOI	10.1016/j.ic.2017.07.003
语种	英语
资助项目	NNSF of China[11531014] ; NNSF of China[11601022] ; Open Fund of Beijing Institute for Scientific and Engineering Computing
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000412282400014
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/26677
专题	应用数学研究所
通讯作者	Wang, Changjun
作者单位	1.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
推荐引用方式 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.