06.19.2023. - 06.23.2023.
Rényi Institute
A research workshop on interactions between singularity theory and low dimensional topology.
For a graph \(G=(V,E)\) with edge weight \(w:E\rightarrow \mathbb{R}^+\), a \(t\)-spanner is a spanning subgraph \(H\) such that for all pair of vertices \(u,v\in V\), we have \(d_H(u,v)\leq t\cdot d_G(u,v)\), where \(d_G(u,v)\) denotes the shortest path distance between vertices \(u\) and \(v\) in \(G\). That is, \(H\) distorts distances in \(G\) by a factor of at most \(t\), which is called the spanning ratio or stretch factor of \(H\).