This project focuses on efficiently solving the P-Way graph partitioning problem using the Multilevel-Kernighan-Lin (KL) algorithm. Graph partitioning is a crucial aspect in various applications, such as parallel algorithm execution, load balancing optimization in computing networks, and intelligent resource management.
-
Sequential Implementation: A sequential version of the Multilevel-KL algorithm has been implemented to provide a baseline for comparison and performance evaluation.
-
Parallel Implementation: The parallel version of the Multilevel-KL algorithm harnesses the power of parallel computing to accelerate the partitioning process on multi-core systems.
-
P-Way Graph Partitioning: The algorithm is tailored to efficiently handle graph partitioning for a specific number of partitions (P-Way).
-
/src: Contains the source code for both sequential and parallel implementations of the Multilevel-KL algorithm. -
/docs: Detailed documentation on the implementation, design choices, and instructions for running and evaluating performance.
- C++ compiler with C++11 or later support.
- Development environment with OpenMP support for the parallel version.
- Clone the repository:
git clone https://github.com/edoardocolella/p-way-graph-partitioning.git - Follow the instructions in the documentation for compiling and running both sequential and parallel implementations.
We welcome contributions from the community! Feel free to open issues to report bugs, propose enhancements, or contribute directly to the code.
Thank you for your interest in the project! We hope it proves valuable for your research or practical application of P-Way graph partitioning.
- Colella Edoardo
- Canavero Serena
- Pavarino Leonardo