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ı: 138
Ö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
- Global optimization of Pt-Cu clusters using a genetic algorithm and density functional theory
Pt-Cu atom topaklarının genetik algoritma ve yoğunluk fonksiyonel teorisi ile global optimizasyonu
EZGİ ERDEM
Yüksek Lisans
İngilizce
2017
Kimya MühendisliğiKoç ÜniversitesiKimya ve Biyoloji Mühendisliği Ana Bilim Dalı
PROF. DR. CAN ERKEY
- Machine learning approach for predicting severity of obstructive sleep apnea syndrome
Obstrüktif uyku apnesinin şiddetinin tahminlenmesinde makine öğrenmesi yaklaşımı
ONURHAN HAMZAOĞLU
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. FETHİYE AYLİN SUNGUR
- Katı yalıtkan malzemelerde elektriksel ve sulu ağaçlanma
Electrical and water treeing in solid insulating materials
AHMET REFİK MARANGOZ
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ÖZCAN KALENDERLİ
- Piyasa etkinliği ve modern portföy kuramı
Efficent markets and modern portfolio theory
İBRAHİM FIÇICIOĞLU
Yüksek Lisans
Türkçe
2002
İşletmeMarmara ÜniversitesiSermaye Piyasası ve Borsa Ana Bilim Dalı
PROF. DR. NİYAZİ BERK
- Hisse senedi analiz yöntemleri, portföy analizi ve bir uygulama
Stock analysis, portfolio management and a study on several stocks of İstanbul stock exchange market
BÜLENT İLHAN