图均匀分割算法研究

作     者：陆逸豪 

作者单位：华东师范大学 

学位级别：硕士

导师姓名：吕长虹

授予年度：2023年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：图均匀分割 启发式算法 NP-困难 Metis软件 

摘      要：图均匀分割问题旨在将图G的顶点集合V分割为大小相近的多个部分V,...,V,满足max|V|≤(1+?)[n/p],?∈R,使得分割后横跨各部分间的割边权和尽可能小.图均匀分割问题是图论的重要问题,在很多工业领域有重要应用.Metis软件是目前使用最为广泛的图分割求解工具,由Karypis实验室开发,对C++和Fortran都有完善的api支持.越来越多的机构希望自主开发图均匀分割求解软件,使得其能够结合自身需求,灵活地在求解结果的好坏与求解速度间进行取舍.本文旨在为自主定制化开发类似Metis软件的图均匀分割求解软件进行算法研究,希望能够在花费时间较Metis软件少的情况下,获得效果相近的分割结果.本文针对小规模图(点数为100-200)和大规模图(点数为10000-20000)进行算法方向的探索.在小规模图上提出了邻域搜索算法,针对边数较多的情况加入了随机抽样.实验中邻域搜索算法在稀疏图上相比Metis软件运行时间平均减少了94.8%,割边权和与Metis软件结果相比平均增大了3.8%.邻域搜索算法在密集图上相比Metis软件运行时间平均减少了61.4%,割边权和与Metis软件结果相比平均减少了0.6%.加入随机抽样的邻域搜索算法在稀疏图上相比Metis软件运行时间平均减少了90.4%,割边权和与Metis软件结果相比平均增大了4.1%.加入随机抽样的邻域搜索算法在密集图上相比Metis软件运行时间平均减少了81.6%,割边权和与Metis软件结果相比平均减少了0.2%.在大规模图上,提出了基于S3收缩的多级分割算法和动态顺序的流式算法.在实验中多级分割算法相比Metis软件运行时间平均分别减少了14.3%,割边权和与Metis软件结果相比平均增加了3.3%.动态顺序的流式算法相比Metis软件运行时间平均减少了68.2%,割边权和与Metis软件结果相比平均增加了5.6%.