Speaker: Uri Zwick Tel Aviv University
Time: 2008-10-22 13:30-2008-10-22 14:30
Venue: FIT Building 4-603, Tsinghua University
Download: Click!
Abstract:
Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We give an O(mn)-time algorithm for solving this problem, which we call the 2-GATHERING problem, where n is the number of vertices and $m$ is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. The 2-gathering problem forms a non-trivial generalization of the non-bipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.
Joint work with Alon Shalita
Short Bio:
Uri Zwick received his B.Sc. degree in Computer Science from the Technion, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.
