Roohani Sharma, Uniform and Constructive Polynomial Kernel for Deletion to
Room B332
IBS (기초과학연구원)
Let
4 events found.
Discrete Math Seminar
Roohani Sharma, Uniform and Constructive Polynomial Kernel for Deletion to
Room B332 IBS (기초과학연구원)Sergey Norin, Asymptotic dimension of intersection graphs
Room B332 IBS (기초과학연구원)The notion of asymptotic dimension of metric spaces, introduced by Gromov, describes their large-scale behaviour. Asymptotic dimension of graph families has been recently studied, in particular, by Bonamy et al. who proved that the asymptotic dimension of proper minor-closed graph families is at most two. We will discuss nerve-type theorems for asymptotic dimension. In particular, …
Mihyun Kang (강미현), TBA
Room B332 IBS (기초과학연구원)Linda Cook, A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
Room B332 IBS (기초과학연구원)A local certification of a graph property is a protocol in which nodes are given “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted, some node in the …