Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Akshay Singh)

The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The application uses recursive search algorithms to start at the beginning and end of the season to search for a valid path. For the parallel algorithm, some preprocessing is done on the input schedules to determine fruitless paths. After the preprocessing, threads within a pool are unleashed to search for valid paths from the multiple possible start cities playing a home game on a given day. The thread pool mechanism is implemented with POSIX threads. The code was intended for Linux OS and includes a makefile to build the application.

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.

There are downloads available under the Creative Commons License license. Download Now
For more complete information about compiler optimizations, see our Optimization Notice.