When initially looking at this problem, I was considering all types of graphs as valid members of my potential data set. The problem here is that most graphs are not three-colorable. In this way, I would find myself looking for extremely rare cases in an infinitely large data set. I chose to limit my set of graphs to only planar graphs in the hope that I would be more likely to find three-colorings among this subclass. Planar graphs are more restricted in their design than non-planar graphs and therefore have a higher probability of being three-colorable. For example a K To attempt to solve this problem on a grid, I first needed to design a method of breaking it into smaller pieces that could be computed at the same time. To do this, I first needed to implement a serial algorithm to three-color graphs. I chose to make this algorithm as general as possible, rather than use various tricks to affect the speed. This basic algorithm took this simple form: - Generate all possible colorings for a graph using three colors.
- Test each of these colorings to see if it was a properly three-colored graph.
The time of this algorithm was O(n This initial algorithm was written recursively, as this was the easiest method. It has been shown that any recursive algorithm can be written in an iterative form and this was the first method of parallelization that I considered. With an iterative algorithm, I could simply run a subset of the iterations on each agent and return a final result. This would have taken the form of distributing n The algorithm I used took a specific approach to graph coloring as opposed to using the general method for parallelizing search. - Break the graph into subgraphs
- For each subgraph
- Generate all possible colorings for a graph using three colors.
- Test each of these colorings to see if it was a properly three-colored graph.
- Recombine the subgraphs two at a time by putting both sets of vertices in one graph and validating three-coloring compatibility
Breaking the graphs into subgraphs was the easiest. My particular test graphs tended to be labeled with vertex numbers relative to their position. Therefore, so as not to lose any generality, I made the distribution of vertices evenly spread over the entire set of vertices. The breaking algorithm does not need to be parallelized as it takes O(n) time. This is quite fast when compared to the other parts of the algorithm. Coloring and checking each subgraph takes the same time as in the basic algorithm, except it now runs on much smaller graphs. We can see that the time per subgraph will be: T The recombination of the graphs is problematic in that it is a multi-step problem. The algorithm for recombining two graphs, A and B, is relatively simple: place the set of all vertices from A and from B into a new graph, then validate all combinations of each graph’s three-colorings with the other’s, finally set the three-colorings of the new graph to any combinations of three-colorings that passed the validation test. The time to combine two subgraphs will be dependant on an unknown function S(j) which is the average number of three-colorings for a planar graph of size j. T = C(s) Because recombination is a multi-step problem we will need to perform this recombination 2 The total run time of this operation is largely dependent on k, n, and p. While n and p are considered fixed for each run, the value to k can be changed to optimize the time. A large value for k would focus more time on the recombination step whereas a small k-value would force longer times on the coloring step and require fewer recombination operations. |