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, ארצות הברית
משך הזמן: 12 אוק׳ 201415 אוק׳ 2014

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך8784

כנס

כנס28th International Symposium on Distributed Computing, DISC 2014
מדינה/אזורארצות הברית
עירAustin
תקופה12/10/1415/10/14

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Brief announcement: Distributed 3/2-approximation of the diameter'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי