En k-kluster av en graf är en ansluten icke-tom subgraf C av radien som mest k, dvs, alla medlemmar av C är inom avstånd k av en viss nod av C, som kallas klusterhuvudet av C. En k-klustering av en graf är en partitionering av grafen till distinkta k-kluster. Att hitta en minsta kardinal k-kluster är känt för att vara N P-hård. I detta dokument föreslår vi en tyst självstabiliserande asynkron distribuerad algoritm för att bygga en k-klustering av alla anslutna nätverk med unika ID. Vår algoritm stabiliseras i O(n) rundor, med hjälp av O(log n) utrymme per process, där n är antalet processer. I det allmänna fallet konstruerar vår algoritm O( n k ) k-kluster. Om nätverket är en Unit Disk Graph (UDG), då vår algoritm är 7.2552k + O(1)-konkurrenskraft, det vill säga antalet kluster konstruerade av algoritmen är högst 7.2552k + O(1) gånger det minsta möjliga antalet k-kluster i alla k-kluster i samma nätverk. Mer allmänt, om nätverket är en ungefärlig Diskgraf (ADG) med approximation förhållande λ, då vår algoritm är 7.2552λ 2 k + O(λ)-konkurrenskraft. Vår lösning är baserad på den självstabiliserande konstruktionen av en datastruktur som kallas MIS Tree, ett spännträd i nätverket vars processer på jämna nivåer bildar en maximal oberoende uppsättning av nätverket. MIS-trädkonstruktionen är tids flaskhalsen för vår k-klustersalgoritm, eftersom det tar rundor i värsta fall, medan resten av algoritmen tar O(D) rundor, där D är nätverkets diameter. Vi skulle vilja förbättra den tiden för att vara O(D), men vi visar att vår distribuerade MIS trädkonstruktion är ett P-komplett problem.
Den algoritm som presenteras i detta dokument liknar den i REF.
Competitive Self-Stabilizing k-Clustering
{'venue': 'ICDCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}