The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
 
                                 Guest Seminar
 
                    Seminar Room, Room 261, Ziskind Building
                          on Sunday, November 27, 2011
                                    at 11:00
 
                                 Jukka Suomela
                             University of Helsinki
 
                                 will speak on
 
                Distributed Maximal Matching: Greedy is Optimal
 
Abstract:
 
We study distributed algorithms that find a maximal matching in an anonymous,
edge-coloured graph. If the edges are properly coloured with k colours, there
is a trivial greedy algorithm that finds a maximal matching in k - 1
synchronous communication rounds. I will show that the greedy algorithm is
optimal in the general case: any algorithm that finds a maximal matching in
anonymous, k-edge-coloured graphs requires k - 1 rounds.
 
As a corollary, we show that the complexity of finding a maximal matching in a
bounded-degree edge-coloured graph is linear in the maximum degree of the
graph. This is the first linear-in-max-degree lower bound for the distributed
complexity of a classical graph problem.
 
This is joint work with Juho Hirvonen.
 
For more information, see  <http://arxiv.org/abs/1110.0367>
 
Host - David Peleg -  <david.peleg@weizmann.ac.il>
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Yaeli Malka   <yaeli.malka@weizmann.ac.il>