Brief announcement: Eccentricities via parallel set cover

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

The eccentricity of a node in a graph G(V, E) is its maximal shortest-path distance to any other node. Shun (KDD 2015) suggested a simple heuristic for computing all eccentricities in an input graph, based on two-phase parallel BFS from a small sample of nodes. It was shown to outperform state-of-the-art algorithms by up to orders of magnitude. This empirical success stands in apparent contrast to recent theoretical hardness results on approximating all eccentricities (Backurs et al., STOC 2018). This note aims to formally explain the performance of this heuristic, by drawing a connection to the streaming Set Cover algorithm of Demaine et al. (DISC 2014). We use it to suggest a variant with similar work and depth bounds, which is guaranteed to compute almost all eccentricities exactly, if the graph satisfies a condition we call small eccentric periphery. The condition can be ascertained for all real-world graph used in Shun (KDD 2015) and in our experiments. Experimental results demonstrate the validity of the analysis and the empirical advantage of our proposed variant.

שפה מקוריתאנגלית
כותר פרסום המארחSPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
עמודים43-45
מספר עמודים3
מסת"ב (אלקטרוני)9781450361842
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 17 יוני 2019
פורסם באופן חיצוניכן
אירוע31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, ארצות הברית
משך הזמן: 22 יוני 201924 יוני 2019

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

שםAnnual ACM Symposium on Parallelism in Algorithms and Architectures

כנס

כנס31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
מדינה/אזורארצות הברית
עירPhoenix
תקופה22/06/1924/06/19

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1708???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Brief announcement: Eccentricities via parallel set cover'. יחד הם יוצרים טביעת אצבע ייחודית.

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