Personal tools
You are here: Home CG seminar 2019 Diameter spanners
« September 2020 »
Log in

Forgot your password?

Diameter spanners

Wednesday, June 12th, 2019, 16:10

Schreiber 309


Diameter spanners

Omer Gold, TAU


The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread throughout data and communication networks. Designing such networks with a sparse (subquadratic) set of edges and small diameter is highly desired. 
Thus, it is a natural question to ask how much can we sparsify a graph while guaranteeing that its diameter is preserved within an approximation factor $t$, for some $t>1$.
To tackle this question, we initiate the study of diameter spanners. Given a directed graph $G = (V, E)$, a subgraph $H = (V, E' \subseteq E)$ is defined to be a $t$-diameter spanner if the diameter of $H$ is at most $t$ times the diameter of $G$. 
We show the existence of (and algorithms to compute) various $t$-diameter spanners with a sparse set of edges and $t<2$, for directed unweighted graphs.
We also give diameter spanner constructions for directed graphs with edge-weights that are at least $1$.
Joint work with Keerti Choudhary 
Document Actions