Att hitta en liten dominerande uppsättning är ett av de mest grundläggande problemen med traditionell grafteori. I detta dokument presenterar vi en ny helt distribuerad approximationsalgoritm baserad på LP avslappningstekniker. För en godtycklig parameter k och maximal grad A beräknar vår algoritm en dominerande uppsättning av förväntad storlek O(kA 2/k log AIDSoPTI) i O(k 2) rundor där varje nod måste skicka O(k2A) meddelanden av storlek O(logA). Detta är den första algoritmen som uppnår ett icke-trivialt approximationsförhållande i ett konstant antal rundor.
Kuhn och Wattenhofer REF föreslog en annan randomiserad algoritm som uppnår en förväntad OðkÁ 2=k log Á
Constant-time distributed dominating set approximation
{'venue': "PODC '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}