En grundläggande fråga som döljer uppkomsten av massiva parallella datorplattformar (MPC) är hur kan den extra kraften i MPC-paradigmet (mer lokal lagring och beräkningskraft) utnyttjas för att uppnå snabbare algoritmer jämfört med klassiska parallella modeller som PRAM? Tidigare forskning har identifierat det glesa graf konnektivitetsproblem som ett stort hinder för sådan förbättring: Medan klassiska logaritmiska-round PRAM algoritmer för att hitta anslutna komponenter i n-vertex graf har varit kända i mer än tre decennier, ingen o (log n)-round MPC algoritmer är kända för denna uppgift med verkligen sublinear i n minne per maskin. Detta problem uppstår vid bearbetning av massiva men ändå glesa grafer med O(n) kanter, för vilka den intressanta inställningen av parametrar är n 1-â(1) minne per maskin. Man antar att det kanske inte är möjligt att uppnå en o(log n)-round-algoritm för konnektivitet på allmänna glesa grafer med n 1-ds(1) per maskinminne, och detta antagande utgör också grunden för flera villkorade hårdhetsresultat på den runda komplexiteten hos andra problem i MPC-modellen. I detta dokument tar vi ett opportunistiskt förhållningssätt till det glesa problemet med grafkonnektivitet, genom att utforma en algoritm med förbättrade prestandagarantier när det gäller konnektivitetsstrukturen i indatagrafen. Formellt designar vi en MPC-algoritm som hittar alla anslutna komponenter med spektralgap minst λ i en graf i O(log log n + log (1/λ)) MPC-rundor och n  på 1) minne per maskin. Även om denna algoritm fortfarande kräver  och (log n) rundor i värsta fall när komponenter är "svag" anslutna (dvs. λ  och 1/n), uppnår den en exponentiell runda minskning på glesa "välanslutna" komponenter (dvs. λ ≥ 1/polylog(n)) med hjälp av endast n  och 1) minne per maskin och O(n) totalt minne, och fungerar fortfarande i o(log n) rundor även när λ = 1/n o(1). Såvitt vi vet är detta den första icke-triviala (och faktiskt exponentiella) förbättringen av den runda komplexiteten över PRAM-algoritmer, för en naturlig klass av glesa konnektivitetsfall.
Mer relevant för vårt arbete med grafanslutning, ett nyligen resultat av Assadi et al. REF innebär en O(log 1 λ + log log n) rund algoritm för grafer med O(n) kanter som har spektralgap minst λ.
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}