1 citations · 2 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2023★ 1 cited
Degrees and Network Design: New Problems and Approximations
Michael Dinitz, Guy Kortsarz, Shi Li
While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an obje…
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…