1. Sergey Voronov
  2. vertex-cover

Overview

It is an implementation of an algorithm for solving vertex cover problem. This problem is np-complete, so my algorithm is a variation of the brute force. Threadpool was used for parallelization.

Presentation (problem, methods and tests)

Pdf file (LaTeX source).

Necessary components

Clang. Plots: Python, Matplotlib, NumPy.

Ubuntu / Mint

$ sudo apt-get install clang python python-matplotlib python-numpy

How to build

$ clang++ -pthread src/*.cpp src/ThreadPool/*.cpp -std=c++0x -o vertex-cover
$ ./vertex-cover 4 

4 -- number_of_threads.

Plots

Folder src/plots contains python scripts. They show some plots, related to tests.

How to run scripts

$ python src/plots/full_graphs_plot.py

A plot exapmle.

Plot example

License

Modified BSD, license file.