Solving the maximum common subgraph problem on many-cores architectures

The Maximum Common Subgraph (MCS) Problem is a well known problem in literature. It has been proved to be an NP-hard problem, then it is often considered as not worthy to search for an exact solution due to its high complexity. Luckily, the ad-vent of newest computing technologies and processors, several algorithms have been developed to efficiently solve very complex problems. Given their still high time consumption, this thesis discusses the possibility to produce a GPU implementation under the CUDA environment of one of the most efficient strategies currently known, namely the McSplit algorithm Despite we find that such implementation it is indeed possible, experimental results showed that, considering the actual state of the CUDA APIs, it may be at least questionable to use this version against a standard CPU-only multi-thread implementation.