En graf har tillväxthastighet k om antalet noder i någon subgraf med diameter r begränsas av O(r k ). Kommunikationsdiagrammen för trådlösa nätverk och peer-to-peer-nätverk har ofta en liten tillväxttakt. I detta dokument studerar vi avvägningen mellan två kvalitetsåtgärder för routing i tillväxtbegränsade diagram. De två åtgärder vi anser vara stretchfaktorn, som mäter längden på routingbanorna, och lastbalansförhållandet, som mäter hur jämnt trafiken fördelas. Vi visar att om routingalgoritmen krävs för att använda banor med stretchfaktor c, då dess lastbalansförhållande begränsas av O(n/c) 1−1/k ), där k är grafens tillväxthastighet. Vi illustrerar våra resultat genom att fokusera på enhetsdiskkurvan för modellering av trådlösa nätverk där två noder har direktkommunikation om deras avstånd ligger under en viss tröskel. Vi visar att om den maximala densiteten av noderna begränsas av ρ, det finns routing schema så att stretchfaktorn för routing vägar är som mest c, och den maximala belastningen på noderna är som mest O(min( ρn/c, n/c) gånger den optimala. Dessutom är belastningsbalansförhållandet snävt i värsta fall. Som ett specialfall, när densiteten begränsas av en konstant, den kortaste vägen routing har en belastning balanserande förhållande av O ( ε n). Resultatet sträcker sig till k-dimensionella enhet bollen grafer och grafer med tillväxthastighet k. Vi diskuterar också algoritmiska frågor för belastning balanserad kort väg routing och för belastning balanserad routing i skiftnyckel grafer.
I en allmän enhet disk graf inställning, det finns en avvägning mellan stretch faktor och belastning balansering förhållandet REF.
Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs
{'venue': "PODC '04", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}