Minimum weighted perfect neighborhood set problem

Yönsüz basit bir çizge G = (V,E) üzerinde, δ(j) ile gösterilen j ∈ V düğümünün açık komşuluk kümesi, j'ye bitişik tüm komşuların kümesi olarak tanımlanır, diğer bir deyişle δ(j) = {i|{i,j} ∈ E}. Δ(j) ile gösterilen j düğümünün kapalı komşuluk kümesi ise Δ(j) = δ(j)∪{j} olarak tanımlanır. Bir küme S ⊆ V için, eğer |Δ(j)∩S|=1 ise j düğümü S'ye göre mükemmel, diğer bir deyişle S-mükemmel kabul edilir. Eğer S-mükemmel düğümler kümesi, G çizgesinin bir baskınlık kümesi ise, S kümesine mükemmel komşuluk kümesi denir. Hedetniemi ve diğ. (1997), G bir ağaç olduğunda en az eleman sayılı mükemmel komşuluk kümesi problemini çözen ve doğrusal zamanda çalışan bir algoritma önerdi. Biz, önerilen algoritmada bazı kusurlar gözlemledik ve bu çalışmada bunları düzelttik. Ayrıca, sorunun ağırlıklı versiyonunu ele alarak bir S mükemmel komşuluk kümesinin ağırlığını ∑j∈V (wjyj + vjxj) ile belirledik. Burada yj ve xj , j'nin S'nin içinde ve S-mükemmel olduğu durumlarda 1 değerini alan ikili değişkenlerdir, ve wj ve vj , j düğümü ile ilişkilendirilen ağırlık değerleridir. Biz önerilen algoritmayı, ağırlıklı versiyonu ele alacak şekilde genişlettik ve algoritmanın doğruluğunu, herhangi bir çizge için önerdiğimiz bir tam sayılı programlama formülasyonundan gelen çözüm değerleri ile kendisinin çözümlerini kıyaslayarak kontrol ettik. Ayrıca, tam sayılı programlama formülasyonunu daha güçlü hale getirmek için ek geçerli eşitsizlikler sağladık, ve bu geçerli eşitsizliklerin yardımıyla yıldız çizgeler ve tam çizgeler için mükemmel komşuluk kümesi politopunu karakterize ettik. Son olarak, bu geçerli eşitsizliklerin etkilerini görmek için hesaplama deneyleri yaptık.