I en följd av de senaste resultaten (PODC 2015 och PODC 2016) förbättrades drifttiden för den snabbaste algoritmen för problemet med minsta spännvidd (MST) i den överbelastade Clique-modellen först till O(log log log n) från O(log log n) (Hegeman et al., PODC 2015) och sedan till O(log * n) (Ghaffari och Parter, PODC 2016). Alla dessa algoritmer använder  till (n 2 ) meddelanden oberoende av antalet kanter i inmatningskurvan. Detta dokument svarar positivt på en fråga som ställdes i Hegeman et al., och presenterar den första "supersnabba" MST-algoritmen med o(m) meddelande komplexitet för inmatningsgrafer med m-kanter. Specifikt presenterar vi en algoritm som körs i O(log * n) rundor med hög sannolikhet, med meddelande komplexitet O( ε m · n) och sedan bygga på denna algoritm för att härleda en familj av algoritmer, som innehåller för alla ε, 0 < ε ≤ 1, en algoritm som kör i O(log * n/ε) rundor med hög sannolikhet, med hjälp av O(n 1+ε /ε) meddelanden. Ställa in ε = log log n/ log n leder till den första underlogaritmen runt överbelastade Clique MST algoritm som använder endast O(n) meddelanden. Våra primära verktyg för att uppnå dessa resultat är (i) en komponent-wise bunden på antalet kandidater för MST kanter, förlänga provtagningen lemma av Karger, Klein, och Tarjan (Karger, Klein, och Tarjan, JACM 1995) och (ii) (log n)-wiseoberoende linjära graf skisser (Cormode och Firmani, Dist. Förbehåll IIIA-PT-17 Databaser, 2014) för att generera MST kandidatkanter.
Minskning av antalet överförda meddelanden i MST-algoritmerna studerades i REF.
Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}