Vertex Connectivity Under Sampling
le 15 septembre 2015
16h00
ENS Rennes, Salle du conseil
Plan d'accès
Intervention de George Giakkoupis (Inria Rennes)
Séminaire du département Informatique et télécommunications.
A fundamental graph-theoretic question is: If we independently sample each node (or edge) of a graph G with some probability p, or equivalently, delete each node (or edge) with probability 1-p, how does the connectivity of the resulting graph compare to that of G? In 1994 Karger answered this question for the case of edge connectivity. I will present the analogous result for vertex connectivity.
This is a joint work with Keren Censor-Hillel, Mohsen Ghaffari, Bernhard Haeupler and Fabian Kuhn, and appeared in SODA'15.
- Thématique(s)
- Formation, Recherche - Valorisation
- Contact
- David cachera
Mise à jour le 9 septembre 2019