Algorithmic Theory of Networks Seminar: George Giakkoupis
Topic
Speakers
Details
A fundamental result by Karger (1994) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = Omega(logn / k) results in a graph that has edge connectivity Omega(kp), with high probability. We prove the analogous result for vertex connectivity when independently sampling vertices. We show that for any k-vertex-connected graph with n nodes, if each node is independently sampled with probability p = Omega(sqrt{logn / k}), then the subgraph induced by the sampled nodes has vertex connectivity Omega(kp^2), with high probability. This bound is existentially optimal.
This is a joint work with Keren Censor-Hillel, Mohsen Ghaffari, Bernhard Haeupler and Fabian Kuhn, and appeared at SODA'15.
Additional Information
Location: ICT 616
This event is part of the PIMS CRG on Algorithmic Theory of Networks.
George Giakkoupis, INRIA
Bio: George Giakkoupis is a Permanent Researcher at INRIA Rennes, in France. He received his PhD from the University of Toronto in 2008, and was a Postdoctoral Fellow at Université Paris 7 and the University of Calgary. His expertise is in the design and analysis of algorithms, in particular, randomized and distributed algorithms. He has worked on epidemic protocols, search in social networks, peer-to-peer networks, and shared-memory distributed computing.