Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Distributed construction of graph spanners
event speaker icon
Ami Paz (Ph.D. Thesis Seminar)
event date icon
Wednesday, 03.05.2017, 12:30
event location icon
Taub 201
event speaker icon
Advisor: Prof. Keren Censor-Hillel
A spanner of a given graph is a sparse subgraph that approximately preserves distances. Since their introduction in the late 1980's, spanners have found numerous applications in synchronization problems, information dissemination, routing schemes and more. Many applications of spanners are in computer networks, where the network needs to find a spanner for its own communication graph. We present distributed algorithms for constructing additive spanners in networks of bounded message size, namely in the CONGEST model. In addition, we present an innovative technique for showing lower bounds for constructing spanners in this setting, a technique that can be useful for other distributed graph problems. This is a part of my phd work, which concentrates on computing distances in distributed systems. Based on joint works with Keren Censor-Hillel, Telikepalli Kavitha, Noam Ravid and Amir Yehudayoff