Proseminar: Computing Maximal Independent Sets an a PRAM

Last year I had a proseminar at university and I do not want the stuff to moulder on my hard drive. It was about randomised algorithms and I had to write about ways to compute maximal independent sets in parallel. The considerations are primarily theoretically, proving runtime complexities on abstract parallel machines—we do not have a problem with using polynomially many cores for a trivial task (we simply have to choose anything that fits) which would in practice be more difficult to distribute to the nodes than computing it sequentially—but it might be interesting to see how randomisation can guarantee uncoupling between different processes resulting in a better runtime complexity, I enjoyed it. What is a maximal independent set? Given a graph it is a subset of the vertices of the graph being both independent and dominating, no two of its members are adjacent, but every other vertex is adjacent to a member of the set—not to be confused with maximum independent sets being maximal independent sets of maximal cardinality, computing maximum independent sets is NP hard. If anybody is interested in a German explanation of randomised parallel computation of maximal independent sets not requiring specific knowledge about the theory parallel or randomised algorithms, here you go (slides).

Leave a Reply

XHTML: Use <blockquote cite="name"> for quotations, <pre lang="text    ∨ cpp-qt ∨ cpp ∨ bash ∨ other language"> for code, [latex] for formulas and <em> for em. Contact me if the comment does not get published, it may have accidentally been marked as spam.

Anti-Spam Quiz: