link Online
Tóm tắt: A spanner of a graph is a spanning subgraph that preserves distances between all pairs of vertices up to some error factor. A spanner of a graph often has less number of edges and smaller total edge weight than the graph itself, which make it useful in many practical applications. There are numerous algorithms in literature for spanner constructions, and the greedy algorithm is arguably the simplest among them. Since its discovery almost 30 years ago, the algorithm has remained mysterious despite a significant research effort.
In this talk, I will introduce the concept of spanners and the greedy algorithm to find a spanner. I then describe several well-known properties of the greedy spanner, survey known results, and mention several open problems in this area.
