/twice-ramanujan-sparsifiers

An implementation and report of the twice Ramanujan graph sparsifiers.

Primary LanguageJupyter NotebookMIT LicenseMIT

Twice Ramanujan Sparsifiers

Based on the paper Twice-Ramanujan Sparsifiers we have implemented a spectral sparsification algorithm that produces graphs with the number of edges being almost linear.

You can check out the full description of the algorithm on the repository website.

Barbel sparsification example

Setup

In a python (>=3.9) environment, run the following commands:

git clone https://github.com/HamidrezaKmK/twice-ramanujan-sparsifiers.git # clone the repository
cd src
pip install -r requirements.txt # install dependencies

License

This project is licensed under the MIT License - see the LICENSE file for details