Compact routing schemes with improved stretch

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

ملخص

We consider the problem of compact routing in weighted general undirected graphs, in which the goal is to construct local routing tables that allow information to be sent on short paths in the network. In this paper the first improvement to the work of Thorup and Zwick [SPAA'01] is presented. Specifically, we construct an improved routing scheme obtaining for every k routing tables of size O (n1/klog D), and stretch (4 - α) k - β for some absolute constants α, β > 0, where D is the normalized diameter. This provides a positive answer to a main open question in this area as to the existence of a routing scheme with stretch c • k for some constant c < 4.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفPODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing
الصفحات33-41
عدد الصفحات9
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2013
منشور خارجيًانعم
الحدث2013 ACM Symposium on Principles of Distributed Computing, PODC 2013 - Montreal, QC, كندا
المدة: ٢٢ يوليو ٢٠١٣٢٤ يوليو ٢٠١٣

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

الاسمProceedings of the Annual ACM Symposium on Principles of Distributed Computing

!!Conference

!!Conference2013 ACM Symposium on Principles of Distributed Computing, PODC 2013
الدولة/الإقليمكندا
المدينةMontreal, QC
المدة٢٢/٠٧/١٣٢٤/٠٧/١٣

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!Hardware and Architecture
  • !!Computer Networks and Communications

قم بذكر هذا