【文件属性】:
文件名称:KaMIS:大型稀疏图的最大独立集和顶点覆盖
文件大小:14.86MB
文件格式:ZIP
更新时间:2021-02-05 05:37:21
algorithm graph reductions datareduction sparse-graphs
KaMIS v2.0
描述
这是开源项目KaMIS-Karlsruhe最大独立集。 给定图G =(V,E),最大独立集问题的目标是计算顶点I的最大基数集合,以使该集合中的任何顶点都不相邻。 这样的集合称为最大独立集合。 这个问题是NP难题,在大型稀疏图中很难解决。
主要项目站点: :
安装
通过运行compile_withcmake.sh来编译源代码。 然后可以在deploy文件夹中找到这些二进制文件。 要编译程序,您需要安装g ++,OpenMP和cmake。
要将图形从DIMACS转换为METIS格式或对其边缘进行排序,可以使用misc文件夹中的python脚本。
我们框架的版本