Fall 2013

Peeling Algorithms

Wednesday, October 23rd, 2013 3:15 pm3:45 pm

Add to Calendar

We describe peeling algorithms, a useful greedy paradigm leading to fast algorithms for big data sets.  With peeling algorithms, typically the problem can be represented as a (random) hypergraph, and vertices and edges are peeled away when the degree of a vertex is at most some fixed amount (usually 1).  In particular, we discuss an analysis for parallel peeling algorithms, which demonstrates that parallel peeling can lead to very fast algorithms in that the peeling completes in O(log log n) rounds when the entire hypergraph can be peeled away.