# Journal of the ACM Bibliography

Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, July 1995. [BibTeX entry]
Abstract

We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V,E). The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, in particular, the following new results:

• For every fixed k, if a graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V^o) expected time or O(V^o log V) worst-case time, where o < 2.376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead of |V| and |E| whenever no confusion may arise.)
• For every fixed k, if a planar graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V) expected time or O(V log V) worst-case time. The same algorithms applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs.
• If a graph G = (V, E) contains a subgraph isomorphic to a bounded tree-width graph H = (V_H, E_H) where |V_H| = O(log V), then such a copy of H can be found in polynomial time. This was not previously known even if H were just a path of length O(log V).
These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can show that it is even in NC. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in: Noga Alon, Raphy Yuster, and Uri Zwick. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 326-335, Montréal, Québec, Canada, 23-25 May 1994.

Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, path and circuit problems

Selected papers that cite this one

Selected references

### Shortcuts:

• Journal of the ACM homepage
• Bibliography top level
• Journal of the ACM Author Index
• Search the HBP database