Color-coding

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), is described. The randomized algorithms obtained using this method can be derandomized using families of perfect hash functio...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1995-07, Vol.42 (4), p.844-856
Main Authors: ALON, N, YUSTER, R, ZWICK, U
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer programming
Computer science
control theory
systems
Exact sciences and technology
Graphs
Information retrieval. Graph
Mathematical models
Mathematics
Studies
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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), is described. The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method obtained, in particular, a number of results are obtained, including that if a graph G = (V, E) contains a subgraph isomorphic to a bounded tree-width graph H = (V subscript H, E subscript H) where the absolute value of V subscript 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). This result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis (1981, 1993) that the LOG PATH problem is in P.
ISSN:0004-5411
1557-735X
DOI:10.1145/210332.210337