"GRAPH ALGORITHMS WITH COLOR CODINGGraph Algorithms with Colour Coding"
In this project, we describe a novel, randomised method proposed by Noga Alon, Raphael Yuster and Uri Zwick, which is the method of color coding, in order to find simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V, E). The randomised algorithms can also be derandomised. Using the color-coding method, we obtain the following results:
- For every fixed k, if a graph G = (V, E) contains a simple cycle of size that is exactly k, such a cycle can be found in polynomial expected time.
- For every fixed k, if a planar graph G containsa simple cycle of size k, it can be found in O (V) expected time. This algorithm also applies to any minor, closed family of graphs.
- If a Graph contains a subgraph that is isomorphic to a bounded tree width graph, this can be found in polynomial time.
These results improve upon the previous results of many authors.
Keywords: derandomisation, perfect Hashing, subgraph isomosphism, tree width.