Analysen av flera algoritmer och datastrukturer kan ramas in som en peeling process på en slumpmässig hypergraf: hörn med grad mindre än k tas bort tills det inte finns några hörn av grad mindre än k vänster. Den återstående hypergrafen är känd som k-kärnan. I den här artikeln analyserar vi parallella peeling processer, där i varje runda, alla hörn av grad mindre än k tas bort. Det är känt att k-kärnan, under en specifik gräns för kanttäthet, är tom med stor sannolikhet. Vi visar att det med stor sannolikhet, under denna tröskel, bara behövs 1 log((k-1)(r-1)) log n + O(1) peelingrundor för att få den tomma k-kärnan för r-uniform hypergrafer. Detta är bundet till en additiv konstant. Intressant nog visar vi att det krävs (log n) peelingrundor ovanför denna tröskel för att hitta den icke-tomma k-kärnan. Eftersom de flesta algoritmer och datastrukturer syftar till att skala till en tom k-kärna, verkar denna asymmetri lyckosam. Vi verifierar de teoretiska resultaten både med simulering och med en parallell implementation med hjälp av grafikprocessorer (GPU). Vår implementering ger insikter i hur man strukturerar parallella skalningsalgoritmer för effektivitet i praktiken.
När det gäller de parallella beräkningarna, Jiang et al. REF införde parallella algoritmer för att hitta det antal iterationer som behövs för att hitta den tomma k-kärnan i slumpmässiga hypergrafer.
Parallel Peeling Algorithms
{'venue': 'TOPC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}