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>