Abstrakt. I den här artikeln anser vi att problemet med att beräkna en minimal vikt vertex-cover i en n-node, viktad, oriktad graf G = (V, E). Vi presenterar en helt distribuerad algoritm för computing vertex täcker av vikt högst två gånger den optimala, i fallet med heltal vikter. Vår algoritm körs i ett förväntat antal O(log n + log på ) kommunikationsrundor, där är den genomsnittliga vertex-vikten. Den tidigare bästa algoritmen för detta problem kräver O(log n(log n + ), rundor och den är inte helt distribuerad. För en maximal matchande M i G, är det ett välkänt faktum att alla vertex-omslag i G måste ha åtminstone. Vår algoritm är baserad på en generalisering av detta kombinatoriella lägre band till den viktade inställningen.
För det viktade fallet ger REF en randomiserad 2-ungeling algoritm i O(log n + log W ) rundor, där W är den maximala vertex vikten.
Distributed weighted vertex cover via maximal matchings
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}