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
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  <>
Host - David Peleg -  <>
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Yaeli Malka   <>