The Locality of Distributed Symmetry Breaking
Add to Google Calendar
We present new methods for solving several classical symmetry breaking
tasks in distributed networks, such as finding maximal independent
sets, maximal matchings, and vertex-colorings.
This is joint work with Leonid Barenboim, Michael Elkin, and Johannes Schneider. An extended abstract appeared in FOCS 2012. PDF available at http://web.eecs.umich.edu/~pettie/papers/Symmetry-Breaking.pdf.