Även om effektiva algoritmer för att hitta minimal avstånd-k dominerande uppsättningar finns, att hitta minimum sådana uppsättningar är NP-hård även för bipartite grafer. Detta dokument presenterar en distribuerad algoritm för att bestämma en minsta (ansluten) distans-k dominerande uppsättning och en maximal avstånd-2k oberoende uppsättning av ett träd T. Det slutar i O(höjd(T)) rundor och använder O(log k) utrymme. Såvitt vi vet är detta den första distribuerade algoritmen som beräknar ett minimum (i motsats till ett minimalt) distansk dominerande set för träd. Algoritmen kan också tillämpas på allmänna grafer, även om avstånd-k dominerande uppsättningar inte nödvändigtvis är minimala.
En distribuerad algoritm för minsta avstånd-k Domination i träd REF.
A Distributed Algorithm for Minimum Distance-k Domination in Trees
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}