Brief announcement: Distributed 3/2-approximation of the diameter

Stephan Holzer, David Peleg, Liam Roditty, Roger Wattenhofer

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We present an algorithm to 3/2-approximate the diameter of a network in time in the CONGESTmodel.We achieve this by combining results of [2,6] with ideas from [7]. This solution is a factor faster than the one achieved in [4] and uses a different approach. Our different approach is of interest as we show how to extend it to compute a (3/2 + ε)-approximation to the diameter in time. This essentially matches the lower bound for (3/2 − ε)-approximating the diameter [1].

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفDistributed Computing - 28th International Symposium, DISC 2014, Proceedings
المحررونFabian Kuhn
ناشرSpringer Verlag
الصفحات562-564
عدد الصفحات3
رقم المعيار الدولي للكتب (الإلكتروني)9783662451731
حالة النشرنُشِر - 2014
الحدث28th International Symposium on Distributed Computing, DISC 2014 - Austin, الولايات المتّحدة
المدة: ١٢ أكتوبر ٢٠١٤١٥ أكتوبر ٢٠١٤

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8784

!!Conference

!!Conference28th International Symposium on Distributed Computing, DISC 2014
الدولة/الإقليمالولايات المتّحدة
المدينةAustin
المدة١٢/١٠/١٤١٥/١٠/١٤

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Brief announcement: Distributed 3/2-approximation of the diameter'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا