Dai, Li och Wu föreslog Rule k, en lokal approximationsalgoritm som försöker hitta en liten ansluten dominerande set i en graf. I det här dokumentet anser vi att två nära relaterade versioner av regel k har en "genomsnittlig" prestanda för modellen med slumpmässiga diskgrafer från n slumpmässiga punkter i en n × n kvadrat. Vi visar att om k ≥ 3 och n = o( ε n), då för båda versionerna av Rule k, den förväntade storleken av Rule k dominerande set är ( 2 n ) som n → ❌. Därav följer att för n i ett lämpligt intervall, den förväntade storleken på regel k dominerande uppsättningar ligger inom en konstant faktor för den optimala.
De kallade denna förbättrade version av algoritmen Rule k. Hansen och Schmutz REF analyserade den förväntade storleken på den producerade anslutna dominerande uppsättningen.
The Expected Size of the Rule k Dominating Set
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}