0 Citations
0 Reads
A note on hardness of diameter approximation
Bringmann Karl
Krinninger Sebastian
Information Processing Letters, 2018, 133: 10-15.
Summary
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, (Omega) over tilde (n) rounds are necessary to compute the diameter (Frischknecht et al., 2012 [2]), where (Omega) over tilde(center dot) hides polylogarithmic factors. Abboud et al. (2016) [3] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer 1
Keywords
Distributed computing; Lower bounds; Hardness in P; Graph algorithms
Institution
--
Select Groups
Select Contacts
swap_vert Order by date
Order by date Order by name