Minimum weighted perfect neighborhood set problem
Minimum ağırlıklı mükemmel komşuluk kümesi problemi
- Tez No: 635011
- Danışmanlar: DR. ÖĞR. ÜYESİ MUSTAFA KEMAL TURAL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Yöneylem Araştırması Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
Given an undirected simple graph G = (V,E), the open neighborhood of a vertex j ∈ V, denoted by δ(j), is defined as the set of all vertices that are adjacent to j , i.e., δ(j) = {i|{i,j} ∈ E}. The closed neighborhood of a vertex j, denoted by Δ(j), is defined as Δ(j) = δ(j)∪{j}. For a set S ⊆ V, a vertex j is said to be perfect with respect to S, i.e., S-perfect, if |Δ(j)∩S|=1. The set S is said to be a perfect neighborhood set if the set of S-perfect vertices dominate G. Hedetniemi et al. (1997) proposed a linear-time algorithm for the minimum cardinality perfect neighborhood set problem when G is a tree. We observe some flaws in the proposed algorithm and correct them. Moreover, we consider the weighted version of the problem, where the weight of a perfect neighborhood set S is defined as ∑j∈V (wjyj + vjxj). Here yj and xj are binary parameters taking the value 1 if and only if j is in S and j is S-perfect, respectively, and wj and vj are the weights associated with vertex j. We extend the algorithm proposed by Hedetniemi et al. for trees to the weighted case and check its correctness by comparing its solutions with the solutions of an integer programming formulation that we propose for arbitrary graphs. Additionally, we provide some valid inequalities for the integer programming formulation to make it stronger, and characterize the perfect neighborhood set polytope for star graphs and complete graphs by the help of these valid inequalities. Finally, we conduct computational experiments to see the effects of these valid inequalities.
Benzer Tezler
- Hücresel yapay sinir ağları için iki öğrenme algoritması ve görüntü işleme uygulamaları
Two learning algorithms for cellular neural networks and their image processing applications
SİNAN KARAMAHMUT
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. CÜNEYT GÜZELİŞ
- Türkiye'de teoride ve uygulamada asgari ücret
Başlık çevirisi yok
NUSRET AĞAOĞLU
Yüksek Lisans
Türkçe
1987
EkonomiUludağ ÜniversitesiÇalışma Ekonomisi ve Endüstri İlişkileri Ana Bilim Dalı
- Organize sanayi bölgelerinde iş güvenliği sorunlarının teknik ve bilimsel araştırılmasında bir yöntem önerisi
Başlık çevirisi yok
MEHMET ALİ YILDIRIM
Yüksek Lisans
Türkçe
1986
Çalışma Ekonomisi ve Endüstri İlişkileriGazi ÜniversitesiKazaların Çevresel ve Teknik Araştırması Ana Bilim Dalı (disiplinlerarası)
DOÇ. DR. İBRAHİM BOYNUKALIN
- Nar konsantresinin dondurularak ve kimyasal yöntemlerle saklanması sırasında meydana gelen değişmeler üzerine bir araştırma
Başlık çevirisi yok
İLHAN BODUR
Yüksek Lisans
Türkçe
1985
Gıda MühendisliğiEge ÜniversitesiTarım Ürünleri Teknolojisi Ana Bilim Dalı
DOÇ. DR. YURDAGEL ÜNAL