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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 17 يونيو 2019
منشور خارجيًانعم
الحدث31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, الولايات المتّحدة
المدة: ٢٢ يونيو ٢٠١٩٢٤ يونيو ٢٠١٩

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

الاسمAnnual ACM Symposium on Parallelism in Algorithms and Architectures

!!Conference

!!Conference31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
الدولة/الإقليمالولايات المتّحدة
المدينةPhoenix
المدة٢٢/٠٦/١٩٢٤/٠٦/١٩

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!Theoretical Computer Science
  • !!Hardware and Architecture

بصمة

أدرس بدقة موضوعات البحث “Brief announcement: Eccentricities via parallel set cover'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا