För en positiv parameter β är det β-bundna avståndet mellan ett par hörn u, v i en viktad oriktad graf G = (V, E, ) längden på den kortaste u − v sökvägen i G med högst β-kanter, aka humle. För β som ovan och Hopsets är en grundläggande graf-teoretisk och graf-algoritmisk konstruktion, och de används ofta för avstånd-relaterade problem i en mängd olika beräkningsinställningar. Befintliga konstruktioner av humleset producerar humleset antingen med kanter av.(n log n) eller med en humleset n.(1). I detta papper vi utformar en konstruktion av linjära storlek humleset med hopbundna (till skillnad från beroendet av  på) (log n) Detta förbättrar den tidigare bundna nästan exponentiellt. Vi utformar också effektiva implementeringar av vår konstruktion i PRAM och distribuerade inställningar. Den enda befintliga PRAM-algoritmen [EN16a] för att beräkna humleset med konstant (dvs. oberoende av n) hopbundet kräver n.(1) tid. Vi utformar en PRAM-algoritm med polylogaritmisk körtid för att beräkna humleset med konstant hopbundna, d.v.s. är vår körtid exponentiellt bättre än den föregående. Dessutom är dessa humleset också betydligt glesare än sina motsvarigheter från [EN16a]. Vi använder våra humleset för att utforma en distribuerad routing schema som uppvisar nära optimal avvägning mellan individuella minneskrav Õ(n 1/k ) av hörn under förbearbetning och routing faser av algoritmen, och stretch O(k), tillsammans med en nära-optimal konstruktionstid  och D + n 1/2+1/k, där D är humlediametern för ingångsgrafen. Tidigare distribuerade routingalgoritmer antingen drabbades av ett oöverkomligt stort minne krav  en ( ε n), eller hade en nära-linjär konstruktionstid, även på grafer med liten hop-diameter D.
Elkin och Neiman REF hävdar en helt kompakt distribuerad routingalgoritm med lågt minne i både förbehandlings- och routingfaserna.
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}