Matching in Parallel

Source code to generate maximum matching in parallel for Solaris platform.

This is the final source code that I generated for my master's degree dissertation. It generates the Maximum Matching of graphs using more than a processor at the same time. At the time that I wrote these codes sources, the equipment that I used was a Sparc 1000 with 8 processors running the Solaris operating system. However, the code allows to use as many processors as available.

The sequential algorithm Micali-Vazirani was the one with the smallest asymptotic curve among all of the others sequential algorithms: (Sqrt (n) m). The main objective my work was to verify if it was possible to develop an algorithm to generate maximum matching faster than the Micali-Vazirani algorithm. The algorithm that I implemented was faster in practically all of the types of the graphs testes. The complete description of this process can be found in my final dissertation.

Along with the source code files, I included the source code to test parallel executions. This test executes a matrix multiplication in parallel. It has the necessary controls over the mutual exclusion areas to guarantee that the results are made calculations properly.