| 基于蚁群优化的多水平图划分算法 |
| |
| 引用本文： | 冷明,郁松年,丁旺,郭强.基于蚁群优化的多水平图划分算法[J].上海大学学报(英文版),2008,12(5):426-432. |
| |
| 作者姓名： | 冷明 郁松年 丁旺 郭强 |
| |
| 作者单位： | [1]School of Computer Engineering and Science, Shanghai University, Shanghai 200072, P. R. China [2]Computer Science Department, Jinggangshan University, Ji＇an 343009, P. R. China |
| |
| 基金项目： | 科技部国际科技合作项目，SEC E-Institute: Shanghai High Institutions Grid |
| |
| 摘 要： | Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed withits guidance function. During the refinement phase, the vertex gain is exploited as ant’s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.
|
| 关 键 词： | 蚁群优化 多水平图 划分算法 计算机技术 |
| 收稿时间： | 2007-06-11 |
| 修稿时间： | 2007-10-12 |
An effective multi-level algorithm based on ant colony optimization for graph bipartitioning |
| |
| LENG Ming,YU Song-nian,DING Wang,GUO Qiang.An effective multi-level algorithm based on ant colony optimization for graph bipartitioning[J].Journal of Shanghai University(English Edition),2008,12(5):426-432. |
| |
| Authors: | LENG Ming YU Song-nian DING Wang GUO Qiang |
| |
| Institution: | 1. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, P. R. China;Computer Science Department, Jinggangshan University, Ji'an 343009, P. R. China
2. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, P. R. China |
| |
| Abstract: | Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant's heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks. |
| |
| Keywords: | rain-cut graph bipartitioning multi-level algorithm ant colony optimization (ACO) |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 |
