首页 | 本学科首页   官方微博 | 高级检索  
     


Strong-Diameter Decompositions of Minor Free Graphs
Authors:Ittai Abraham  Cyril Gavoille  Dahlia Malkhi  Udi Wieder
Affiliation:1. Hebrew University of Jerusalem, Jerusalem, Israel
2. University of Bordeaux, Bordeaux, France
3. Microsoft Research, Silicon Valley Center, Mountain View, CA, USA
Abstract:We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have strong diameter bounds; i.e. each set of the cover/partition has a small diameter as an induced sub-graph. Using these results we provide improved distributed name-independent routing schemes. Specifically, given a graph excluding a minor on r vertices and a parameter ρ>0 we obtain the following results: (1) a polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of O(r 2 ρ) and each vertex belongs to 2 O(r) r! clusters; (2) a name-independent routing scheme with a stretch of O(r 2), headers of O(log n+rlog r) bits, and tables of size 2 O(r) r! log 4 n/log log n bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter O(r6 r ρ) and the probability an edge (u,v) is cut is O(rd(u,v)/ρ).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号