ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE COUNTING OF SUBGRAPHS:
Reports tagged with Approximate counting of subgraphs:
TR09-012 | 4th February 2009
Noga Alon, Shai Gutner

Balanced Hashing, Color Coding and Approximate Counting

Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a given ... more >>>




ISSN 1433-8092 | Imprint