摘要：超大规模集成电路（VLSI）划分问题,属于NP-难问题。结合了贪心随机自适应搜索过程（GRASP）和多级聚类方法的思想,提出了一种基于多级聚类的电路划分算法。算法采用贪心随机自适应的思想改进了多级划分方法中重边粗化聚类（HEM）方法。通过对ISPD98的18个标准测试样例的测试结果表明,该方法与著名的划分工具h Metis相比,划分质量有一定的提高,最多可以改进3%左右。

关键词：vlsi 电路划分 多级聚类 grasp 

单位：福州大学数学与计算机科学学院; 福建福州350116