A generic queuing system and time-saving region restrictions for calculating the crossing number of K(n).

摘要

With the availability of inexpensive computer clusters it is now economically feasible to use parallel processing to attack computationally intensive problems such as calculating the crossing number of a graph. In 1996 Harris and Harris presented an algorithm for solving the crossing number problem of complete graphs, which was implemented in parallel by Tadjiev and Harris a year later. Their algorithm, though parallelized, was not load balanced and did not prune the search space with additional restrictions.; This thesis introduces an easily adaptable parallel work queue combined with a more restrictive algorithm to solve crossing number problems. Implementation of the parallel work queue offers an opportunity to get better results than previously possible on crossing number problems. Meanwhile, we also use this more restrictive algorithm to verify the efficiency of our parallel queuing system. Both the algorithm implementation and analysis are given in this thesis.