Skip to main content
x

Focused Week: Geometric Spanners

10.23.2023. - 10.29.2023.
Rényi Institute

Description

This focused week is part of the special semester on Discrete Geometry and Convexity.

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\). The primary focus of this week lies in the regime \(t=1+\varepsilon\) for arbitrarily small \(\varepsilon>0\). It will explore the asymptotic behavior of graph parameters of geometric \((1+\varepsilon)\)-spanners as \(\varepsilon\) tends to zero.

 

Organizers

Csaba D. Toth (California State University Northridge)
 

Invited Speakers

Sujoy Bhore (IIT Bombay)
Hung Le (University of Massachusetts Amherst)

Participants

Sujoy Bhore
Adrian Dumitrescu
Balázs Keszegh
Gergely Kiss
Hung Le
Alexandre Louvet
Nabil Mustafa
Anurag Murty
Csaba D. Tóth
Géza Tóth
Zsolt Lángi