Аннотация:
Рассмотрим неориентированный взвешенный граф с уникальными кратчайшими путями. Будем изучать маленькие множества вершин, которые задевают все кратчайшие пути из $\epsilon n$ вершин. В докладе будут рассмотрены разные оценки на размеры этих множеств и будут рассказаны два конкретных приложения: точный оракул больших расстояний и вложение метрик в $\ell_1$, которое сохраняет большие расстояния. Результат про метрики дает некоторое улучшение алгоритма Лейтона–Рао для задачи о разреженном разрезе.
|
