Den överbelastade Clique är en distribuerad modell för en-hop nätverk med begränsad bandbredd som har studerats mycket intensivt nyligen. Den modellerar ett nätverk med en n-vertex graf där varje par hörn kan kommunicera en med en annan genom att överföra O(log n) bitar i varje runda. Olika problem har studerats i denna miljö, men för vissa av dem är de mest kända resultaten de för allmänna nätverk. För andra problem, resultaten för överbelastade klichéer är bättre än på allmänna nätverk, men fortfarande ådrar sig betydande beroende av antalet hörn n. Därför prestanda av dessa algoritmer kan bli dålig på stora klichéer, även om deras diameter är bara 1. I detta papper vi utformar betydligt förbättrade algoritmer för olika symmetri-brytande problem, såsom skog-nedbrytningar, vertex-färger, och maximal oberoende uppsättning. Vi analyserar drifttiden för våra algoritmer som en funktion av Arboricity a av en klick subgraph som ges som ingång. Arboriciteten är alltid mindre än antalet hörn n i subgrafen, och för många familjer av grafer är den betydligt mindre. I synnerhet träd, plana grafer, grafer med konstant genus, och många andra grafer har avgränsat arboricity, men obegränsad storlek. Vi får O(a)-skogsnedbrytningsalgoritm med O(log a) tid som förbättrar den tidigare kända O(log n) tid, O(a 2 + )-färgning i O(log * n) tid som förbättrar på en O(log n)-tidsalgoritm, O(a)-färgning i O(a) )-tid som förbättrar på flera tidigare algoritmer, och en maximal oberoende uppsättning algoritm med O( ε a) tid som förbättrar minst kvadratiskt på state-of-the-art för små och måttliga värden av a. Dessa resultat uppnås med hjälp av flera tekniker. Först producerar vi en skogsdekomposition med en användbar struktur som kallas H-partition inom O(logga a) rundor. I allmänhet grafer denna struktur kräver  till (log n) tid, men i överbelastade klichéer kan vi beräkna det snabbare. Vi använder denna struktur i samband med partitionering tekniker som gör att vi kan lösa olika symmetri-brytande problem effektivt.
Särskilt visar Barenboim och Khazanov REF hur man löser en mängd olika grafproblem i den överbelastade klichén effektivt med tanke på sådana grafer, t.ex. beräkna en O(a)-orientering i tiden O(log a), en MIS i tiden O( ε a) och en O(a)-färgning i tiden O(a ε ).
Distributed Symmetry-Breaking Algorithms for Congested Cliques
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}