版权说明 操作指南
首页 > 成果 > 详情

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

认领
导出
下载 Link by DOI
反馈
分享
QQ微信 微博
成果类型:
期刊论文、会议论文
作者:
Li, Wenjun;Cao, Yixin;Chen, Jianer;Wang, Jianxin*
通讯作者:
Wang, Jianxin
作者机构:
[Li, Wenjun; Wang, Jianxin] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.
[Li, Wenjun] Changsha Univ Sci & Technol, Sch Comp & Commun Engn, Hunan Prov Key Lab Intelligent Proc Big Data Tran, Changsha, Hunan, Peoples R China.
[Cao, Yixin] Hong Kong Polytech Univ, Dept Comp, Hong Kong, Hong Kong, Peoples R China.
[Chen, Jianer] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX USA.
通讯机构:
[Wang, Jianxin] C
Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.
语种:
英文
关键词:
Maximum internal spanning tree;Parameterized computation;Local search
期刊:
Information and Computation
ISSN:
0890-5401
年:
2017
卷:
252
页码:
187-200
会议名称:
25th Conference on Concurrency Theory (CONCUR) held jointly with the 9th International Symposium on Trustworthy Global Computing (TGC) / 8th International IFIP Conference on Theoretical Computer Science (IFIP-TCS)
会议时间:
SEP 02-05, 2014
会议地点:
Rome, ITALY
会议主办单位:
[Li, Wenjun;Wang, Jianxin] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.^[Li, Wenjun] Changsha Univ Sci & Technol, Sch Comp & Commun Engn, Hunan Prov Key Lab Intelligent Proc Big Data Tran, Changsha, Hunan, Peoples R China.^[Cao, Yixin] Hong Kong Polytech Univ, Dept Comp, Hong Kong, Hong Kong, Peoples R China.^[Chen, Jianer] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX USA.
会议赞助商:
IFIP
出版地:
525 B ST, STE 1900, SAN DIEGO, CA 92101-4495 USA
出版者:
ACADEMIC PRESS INC ELSEVIER SCIENCE
基金类别:
Supported in part by the National Natural Science Foundation of China (NSFC) under grant 61572414 and the Hong Kong Research Grants Council (RGC) under grant 252026/15E.
机构署名:
本校为其他机构
院系归属:
计算机与通信工程学院
摘要:
The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an O⁎(8k)-time parameterized algorithm. Using depth-2 local search, Knauer and Spoer...

反馈

验证码:
看不清楚,换一个
确定
取消

成果认领

标题:
用户 作者 通讯作者
请选择
请选择
确定
取消

提示

该栏目需要登录且有访问权限才可以访问

如果您有访问权限,请直接 登录访问

如果您没有访问权限,请联系管理员申请开通

管理员联系邮箱:yun@hnwdkj.com