کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874209 | 1441029 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on hardness of diameter approximation
ترجمه فارسی عنوان
توجه به سختی تقریبی قطر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, ΩË(n) rounds are necessary to compute the diameter (Frischknecht et al., 2012 [2]), where ΩË(â
) 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â¤ââ¤polylog(n), distinguishing between networks of diameter 4â+2 and 6â+1 requires ΩË(n) rounds. We slightly tighten this result by showing that even distinguishing between diameter 2â+1 and 3â+1 requires ΩË(n) rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 133, May 2018, Pages 10-15
Journal: Information Processing Letters - Volume 133, May 2018, Pages 10-15
نویسندگان
Karl Bringmann, Sebastian Krinninger,