Near-Maximum Independent Set

This repository implements the near-maximum independent set computation algorithms proposed in our SIGMOD 2017 paper. If you are using the code, please cite our paper.

Lijun Chang, Wei Li and Wenjie Zhang.
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling.
SIGMOD Conference 2017

Compile the code

$ make clean
$ make

Run the code

Different algorithms can be invoked by executing “mis”.

./mis {alg} {graph_directory}

alg is chosen from “greedy, greedy_dynamic, BDOne, BDTwo, LinearTime, NearLinear”

For example,

./mis LinearTime datasets/CA-GrQc

Data format

Each graph is represented by two binary files, b_adj.bin and b_degree.bin (e.g. datasets/CA-GrQc/b_adj.bin and datasets/CA-GrQc/b_degree.bin). More details of the data format can be found in https://lijunchang.github.io/Cohesive_subgraph_book/datasets