Vi presenterar en ny distribuerad algoritm för maximal oberoende uppsättning problem (Detta är en utökad tidskrift version av Schneider och Wattenhofer i tjugosjunde årliga ACM SIGACT-SIGOPS symposium om principer för distribuerad dator, 2008). På avgränsad-oberoende grafer vår deterministiska algoritm slutar i O(log * n) tid, n är antalet noder. Mot bakgrund av Linials (log * n) nedre gräns är vår algoritm asymptotiskt optimal. Dessutom löser den det anslutna dominerande set problemet för enhet disk grafer i O(log * n) tid, exponentiellt snabbare än den state-of-the-art algoritm. Med en ny förlängning vår algoritm beräknar också en δ + 1 färg och en maximal matchning i O(log * n) tid, där δ är den maximala graden av grafen.
Schneider och Wattenhofer presenterar en deterministisk algoritm som beräknar i O(log * n) rundar en ansluten distans-1 dominerande uppsättning med konstant approximation förhållande för avgränsade oberoende grafer REF.
An optimal maximal independent set algorithm for bounded-independence graphs
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}