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]

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:

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


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