Partager cette page :

Vertex Connectivity Under Sampling

le 15 septembre 2015


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.

Séminaire 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.

Formation, Recherche - Valorisation
David cachera

Mise à jour le 9 septembre 2019