En effektiv distribuerad konstruktion av en maximal oberoende uppsättning (MIS) av en graf är av grundläggande betydelse. Vi studerar problemet i klassen Growth-Bounded Graphs, som till exempel inkluderar de välkända Unit Disk Graphs. I motsats till den snabbaste (tidsoptimala) befintliga metoden [11] utgår vi från att ingen geometrisk information (t.ex. avstånd i grafens inbäddning) ges. I stället använder noder randomisering för sina beslut. Vår algoritm beräknar en MIS i O(log log n · log * n) rundor med mycket hög sannolikhet för grafer med begränsad tillväxt, där n betecknar antalet noder i grafen. Med tanke på Linials (log * n) nedre gräns för beräkning av ett MIS i ringnät [12], som utvidgades till randomiserade algoritmer oberoende av Naor [18] och Linial [13], är vår lösning nära till optimal. I ett nötskal visar vår algoritm att för att beräkna en MIS är randomisering ett praktiskt alternativ till distansinformation.
Den för närvarande snabbast randomiserade algoritmen av Gfeller och Vicari REF körs i O(log log n · log * n) tid.
A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
{'venue': "PODC '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}