Color-coding

In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. Color-coding also applies to the detection of cycles of a given length, and more generally it applies to the subgraph isomorphism problem (an NP-complete problem), where it yields polynomial time algorithms when the subgraph pattern that it is trying to detect has bounded treewidth. The color-coding method was proposed and analyzed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick.