1 citations · 1 across the 2 of their papers we have counts for
2 papers
cs.DS2016
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Eden Chlamtáč, Michael Dinitz, Guy Kortsarz +1
It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), dist…
cs.DS2012★ 1 cited
Label Cover instances with large girth and the hardness of approximating basic k-spanner
Michael Dinitz, Guy Kortsarz, Ran Raz
We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some , the problem is roughly…