Loading...

Summer Research Fellowship Programme of India's Science Academies

"GRAPH ALGORITHMS WITH COLOR CODINGGraph Algorithms with Colour Coding"

N. Shriya Reddy

National Institute of Technology, Agartala

Prof. K.S. Mallukarjuna Rao

Indian Insitute of Technology, Bombay, Powai, 400076

Abstract

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.

More
Written, reviewed, revised, proofed and published with