Kernelization via Sampling with Applications to Dynamic Graph Streams

Abstrakt

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce.

Klíčová slova

• Kernelization
• Sampling