Abstract:
Abstract: Spanners are subgraphs that preserve the distances in the original graph within a constant factor called the stretch-factor. In this talk we consider the problem of maintaining a t-spanner in an online model, where n points arrive one by one and the algorithm has to decide which edges need to be added to the spanner to (approximately) preserve the distances. We cover some background and the known results in the offline setting, then we define the competitive ratio for an online Euclidean t-spanner. Finally, we introduce two of the known recent lower bounds on the competitive ratio an online Euclidean t-spanner.Based on a joint work with: Sujoy Bhore, Arnold Filtser, Csaba D. Tóth