Parallel algorithm to solve Maximum Independent Set problem (Bradley Kuszmaul)

The included source code finds a Maximum Independent Set (MIS) of a given graph, as described in the included problem description text file. The included write-up gives an overview of Cilk++ and some of the tools available for Cilk programming. The serial algorithm is a recursive search of paths with and without nodes in the MIS. However, an upper bound on the size of the MIS and the degree of nodes is proved used within this basic algorithm. The parallelization was done with Cilk++ and involves spawning search tasks for the two recursive calls from the serial code. The code was intended for Linux OS and includes a makefile to build the applications.

DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

Есть файлы для загрузки, доступные на условиях лицензии Creative Commons License. Загрузить сейчас

Включить в RSS: 

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.
Возможность комментирования русскоязычного контента была отключена. Узнать подробнее.