Motiverade av routing frågor i ad hoc-nätverk, presenterar vi polylogaritmisk-tid distribuerade algoritmer för två problem. Med tanke på ett nätverk, visar vi först hur man beräknar anslutna och svagt anslutna dominerande uppsättningar vars storlek är som mest O (log ) gånger den optimala, är den maximala graden av inmatningsnätet. Detta är bäst möjligt om NP DTIME[n O(log log n) ] och om processorer krävs för att köra i polynom-tid. Vi visar sedan hur man konstruerar dominerande uppsättningar som har ovanstående egenskaper, samt den "low stretch" egenskapen att två angränsande noder i nätverket har sina dominatorer på ett avstånd av högst O (log n) i utgångsnätet. (Ges en dominerande uppsättning S, en dominator av en vertex u är någon v  och S sådan att avståndet mellan u och v är som mest en.) Vi visar också att våra tidsramar är i stort sett optimala.
Dubhashi m.fl. REF föreslår en distribuerad algoritm som hittar en Oðlog Á ska approximation till den minsta CDS i Oðlog n log Á på tiden.
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}