A&C Seminar: Greg Bodwin - Turán-type problems in graph metric sparsification
Автор: U Waterloo A&C Seminar
Загружено: 2024-12-16
Просмотров: 105
Описание:
In extremal combinatorics, a Turán-type problem is one that asks for the maximum possible size of a graph that avoids one or more forbidden subgraphs. These are named for Turán's Theorem from 1941, which solves the problem for cliques.
In theoretical computer science, a graph metric sparsification problem is one that asks how many edges we can generally remove from a graph while approximately preserving its distance or reachability properties.
We will survey a recent line of work connecting these areas, which approaches graph metric sparsification through the lens of forbidden subgraphs. No prior knowledge of either area is assumed.
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
