中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 期刊论文
题名:
GPP问题的骨架分析与启发式算法设计
其他题名: backbone analysis and heuristic design for the graph partitioning problem
作者: 江贺 ; 邱铁
关键词: 图的划分问题
刊名: 计算机学报
发表日期: 2009
卷: 32, 期:8, 页:1662-1667
收录类别: 其他
部门归属: 大连理工大学软件学院,大连,辽宁,116621;中国科学院软件研究所计算机科学国家重点实验室,北京,100190;大连理工大学软件学院,大连,辽宁,116621
摘要: 图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.
语种: 中文
内容类型: 期刊论文
URI标识: http://ir.iscas.ac.cn/handle/311060/8002
Appears in Collections:计算机科学国家重点实验室 _期刊论文

Files in This Item:
File Name/ File Size Content Type Version Access License
GPP问题的骨架分析与启发式算法设计.pdf(493KB)----限制开放-- 联系获取全文

Recommended Citation:
江贺,邱铁. GPP问题的骨架分析与启发式算法设计[J]. 计算机学报,2009-01-01,32(8):1662-1667.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[江贺]'s Articles
[邱铁]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[江贺]‘s Articles
[邱铁]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

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

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace