All reports by Author Shai Gutner:

__
TR09-012
| 4th February 2009
__

Noga Alon, Shai Gutner#### Balanced Hashing, Color Coding and Approximate Counting

__
TR08-066
| 16th July 2008
__

Noga Alon, Shai Gutner#### Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

Noga Alon, Shai Gutner

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 ...
more >>>

Noga Alon, Shai Gutner

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves ...
more >>>