Personal tools
You are here: Home CG seminar 2019 Diameter spanners
« August 2019 »
August
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728293031
Log in


Forgot your password?
 

Diameter spanners

Wednesday, June 12th, 2019, 16:10

Schreiber 309

underline

Diameter spanners

Omer Gold, TAU

Abstract: 

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