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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2013
פורסם באופן חיצוניכן
אירוע2013 ACM Symposium on Principles of Distributed Computing, PODC 2013 - Montreal, QC, קנדה
משך הזמן: 22 יולי 201324 יולי 2013

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

שםProceedings of the Annual ACM Symposium on Principles of Distributed Computing

כנס

כנס2013 ACM Symposium on Principles of Distributed Computing, PODC 2013
מדינה/אזורקנדה
עירMontreal, QC
תקופה22/07/1324/07/13

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1705???

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