À¶Ý®ÊÓƵ

Title: Approximating Distances on Undirected Graphs

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýThe shortest path metric on undirected graphs is a fundamental quantity with deep connections to combinatorics and structural graph theory. Tools built around such approximations are playing increasingly important role in efficient optimization algorithms and data structures. This talk will introduce such approximations starting from the breadth first search tree, and build upon them to discuss distance oracles and oblivious routings.